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: h19b5812fa8c8079a
Venue: PODS
Year: 2015
Pagerank: 5.0580396e-05
Overall Rank: 10,219 | 31.30%
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,500	Crowdsourced Data Management: Overview and Challenges	2017	SIGMOD	5.5083793e-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
266	Human-powered Sorts and Joins	2012	VLDB	0.00022739124
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021311041
749	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014265279
1,124	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011927351

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,566	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD
2	3,340	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD
3	12,755	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
4	9,701	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD
5	2,491	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
6	12,962	On Dominating Your Neighborhood Profitably	2007	VLDB
7	256	Efficient Progressive Skyline Computation	2001	VLDB
8	5,626	Reconciling Skyline and Ranking Queries	2017	VLDB
9	1,394	Efficient Computation of the Skyline Cube	2005	VLDB
10	9,502	Computing All Skyline Probabilities for Uncertain Data	2009	PODS