Skyline Queries with Noisy Comparisons

Summary: Introduces a noisy-comparison model for skyline queries (pairwise comparisons may err; confidence via repetition) and gives the first output-sensitive algorithms that minimize comparisons and rounds to compute/verify skylines w.h.p. Shows optimal skyline prediction from partial noisy comparisons is computationally intractable. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1659
Venue: PODS
Year: 2015
Pagerank: 5.1741314e-05
Overall Rank: 10,030 | 31.19%
DOI: 10.1145/2745754.2745775

Incoming Non-self Citations Over Time

Authors

1. Benoit Groz (INRIA; Paris-Sud University; Tel Aviv University)
2. Tova Milo (Tel Aviv University)

BibTeX Citation

@inproceedings{groz_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Skyline Queries with Noisy Comparisons}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745775},
        doi = {10.1145/2745754.2745775},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Groz, Benoit and Milo, Tova},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,357	Crowdsourced Data Management: Overview and Challenges	2017	SIGMOD	5.6346837e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
265	Human-powered Sorts and Joins	2012	VLDB	0.00022935368
308	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021787597
743	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014421358
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,516	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD
2	3,273	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD
3	12,464	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
4	9,524	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD
5	2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
6	12,672	On Dominating Your Neighborhood Profitably	2007	VLDB
7	243	Efficient Progressive Skyline Computation	2001	VLDB
8	5,496	Reconciling Skyline and Ranking Queries	2017	VLDB
9	1,360	Efficient Computation of the Skyline Cube	2005	VLDB
10	9,323	Computing All Skyline Probabilities for Uncertain Data	2009	PODS