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,117 | Crowdsourced Data Management: Overview and Challenges | 2017 | SIGMOD | 4.826509e-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 |
|---|---|---|---|---|
| 267 | Human-powered Sorts and Joins | 2012 | VLDB | 0.00029690405 |
| 386 | Shooting Stars in the Sky: An Online Algorithm for Skyline Queries | 2002 | VLDB | 0.00024768022 |
| 859 | So Who Won? Dynamic Max Discovery with the Crowd | 2012 | SIGMOD | 0.00015870894 |
| 1,179 | Probabilistic Skylines on Uncertain Data | 2007 | VLDB | 0.00013457451 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,695 | Scalable Skyline Computation Using Object-based Space Partitioning | 2009 | SIGMOD | 5.3681018e-05 |
| 3,452 | Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates | 2006 | SIGMOD | 7.0821774e-05 |
| 12,269 | Efficient Skyline Evaluation over Partially Ordered Domains | 2010 | VLDB | 4.1945683e-05 |
| 9,452 | Output-sensitive Evaluation of Prioritized Skyline Queries | 2015 | SIGMOD | 4.339214e-05 |
| 2,500 | Efficient Skyline Computation over Low-Cardinality Domains | 2007 | VLDB | 8.6457563e-05 |
| 12,479 | On Dominating Your Neighborhood Profitably | 2007 | VLDB | 4.1945683e-05 |
| 262 | Efficient Progressive Skyline Computation | 2001 | VLDB | 0.00029987552 |
| 6,091 | Reconciling Skyline and Ranking Queries | 2017 | VLDB | 5.214376e-05 |
| 1,575 | Efficient Computation of the Skyline Cube | 2005 | VLDB | 0.00011286884 |
| 9,165 | Computing All Skyline Probabilities for Uncertain Data | 2009 | PODS | 4.3849295e-05 |