Name
Abstract | ||
|---|---|---|
Given a set of n points in a d-dimensional space, we seek to compute the skyline, i.e., those points that are not strictly dominated by any other point, using few comparisons between elements. We study the crowdsourcing-inspired setting ([FRPU94]) where comparisons fail with constant probability. In this model, Groz u0026 Milo [GM15] show three bounds on the query complexity for the skyline problem. We provide two output-sensitive algorithms computing the skyline with query complexity O(nd log(dk)) and O(ndk log(k)), where k is the size of the skyline. These results improve significantly on the state-of-the-art and are tight for low dimensions. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Data Structures and Algorithms | Skyline,Theoretical computer science,Skyline computation,Mathematics |
DocType | Volume | Citations |
Journal | abs/1710.02058 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frederik Mallmann-Trenn | 1 | 34 | 13.05 |
| Claire Mathieu | 2 | 452 | 25.78 |
| Víctor Verdugo | 3 | 12 | 5.03 |