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)
Incoming Non-self Citations Over Time
Authors
- 1. Benoit Groz
- 2. Tova Milo
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,116 | Crowdsourced Data Management: Overview and Challenges | 2017 | SIGMOD | 4.8219732e-05 |
Previous
Page 1 / 1
Next
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.00029884758 |
| 386 | Shooting Stars in the Sky: An Online Algorithm for Skyline Queries | 2002 | VLDB | 0.00024740283 |
| 854 | So Who Won? Dynamic Max Discovery with the Crowd | 2012 | SIGMOD | 0.00015879917 |
| 1,181 | Probabilistic Skylines on Uncertain Data | 2007 | VLDB | 0.00013447487 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,873 | Stratified Computation of Skylines with Partially-Ordered Domains | 2005 | SIGMOD | 7.9777806e-05 |
| 3,454 | Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates | 2006 | SIGMOD | 7.0770352e-05 |
| 12,277 | Efficient Skyline Evaluation over Partially Ordered Domains | 2010 | VLDB | 4.1905499e-05 |
| 9,376 | Output-sensitive Evaluation of Prioritized Skyline Queries | 2015 | SIGMOD | 4.344689e-05 |
| 2,502 | Efficient Skyline Computation over Low-Cardinality Domains | 2007 | VLDB | 8.631993e-05 |
| 12,488 | On Dominating Your Neighborhood Profitably | 2007 | VLDB | 4.1905499e-05 |
| 262 | Efficient Progressive Skyline Computation | 2001 | VLDB | 0.00029962961 |
| 6,090 | Reconciling Skyline and Ranking Queries | 2017 | VLDB | 5.214198e-05 |
| 1,576 | Efficient Computation of the Skyline Cube | 2005 | VLDB | 0.00011278557 |
| 9,167 | Computing All Skyline Probabilities for Uncertain Data | 2009 | PODS | 4.380727e-05 |