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.0556452e-05
Overall Rank: 10,225 | 31.28%
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,505	Crowdsourced Data Management: Overview and Challenges	2017	SIGMOD	5.5057737e-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.00022735106
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021301023
750	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014258988
1,125	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011921893

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,761	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
4	2,491	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
5	9,706	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD
6	12,968	On Dominating Your Neighborhood Profitably	2007	VLDB
7	256	Efficient Progressive Skyline Computation	2001	VLDB
8	5,627	Reconciling Skyline and Ranking Queries	2017	VLDB
9	1,395	Efficient Computation of the Skyline Cube	2005	VLDB
10	9,513	Computing All Skyline Probabilities for Uncertain Data	2009	PODS