Randomized Multi-pass Streaming Skyline Algorithms

Summary: RAND is the first randomized skyline algorithm, using multi-pass streaming over external data without preprocessing and achieving near-optimal worst-case performance. It is distributable, supports partially ordered attributes, and remains robust under data variations. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10077
Venue: VLDB
Year: 2009
Pagerank: 6.4333573e-05
Overall Rank: 4,941 | 66.11%
DOI: 10.14778/1687627.1687638

Incoming Non-self Citations Over Time

Authors

1. Atish Das Sarma (Georgia Institute of Technology)
2. Ashwin Lall (Georgia Institute of Technology)
3. Danupon Nanongkai (Georgia Institute of Technology)
4. Jun Xu (Georgia Institute of Technology)

BibTeX Citation

@article{sarma_vldb09,
        title = {{Randomized Multi-pass Streaming Skyline Algorithms}},
        author = {Sarma, Atish Das and Lall, Ashwin and Nanongkai, Danupon and Xu, Jun},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687638},
        url = {https://doi.org/10.14778/1687627.1687638},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,016	On Finding Skylines in External Memory	2011	PODS	6.3998091e-05
8,029	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.5045998e-05
8,312	Skyline Operator on Anti-correlated Distributions	2013	VLDB	5.4556836e-05
8,750	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.3766157e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
243	Efficient Progressive Skyline Computation	2001	VLDB	0.00023495903
308	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021787597
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.5839844e-05
2,516	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD	8.4773324e-05
5,409	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	6.2279841e-05
8,488	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.4153038e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,516	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD
2	2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
3	12,464	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
4	4,472	Relative Error Streaming Quantiles	2021	PODS
5	3,409	Approaching the Skyline in Z Order	2007	VLDB
6	5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
7	5,016	On Finding Skylines in External Memory	2011	PODS
8	9,323	Computing All Skyline Probabilities for Uncertain Data	2009	PODS
9	6,616	Categorical Skylines for Streaming Data	2008	SIGMOD
10	10,030	Skyline Queries with Noisy Comparisons	2015	PODS