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: hb2209008a782656d
Venue: VLDB
Year: 2009
Pagerank: 6.2890477e-05
Overall Rank: 5,070 | 65.92%
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,144	On Finding Skylines in External Memory	2011	PODS	6.2566665e-05
8,189	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.3810913e-05
8,479	Skyline Operator on Anti-correlated Distributions	2013	VLDB	5.3332727e-05
8,913	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.2559789e-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
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
256	Efficient Progressive Skyline Computation	2001	VLDB	0.00022981799
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021311041
1,124	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011927351
2,491	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.3921786e-05
2,566	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD	8.288424e-05
5,548	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	6.0882467e-05
8,656	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.2938008e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,566	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD
2	2,491	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
3	12,755	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
4	4,564	Relative Error Streaming Quantiles	2021	PODS
5	3,478	Approaching the Skyline in Z Order	2007	VLDB
6	5,590	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
7	5,144	On Finding Skylines in External Memory	2011	PODS
8	9,502	Computing All Skyline Probabilities for Uncertain Data	2009	PODS
9	6,745	Categorical Skylines for Streaming Data	2008	SIGMOD
10	10,219	Skyline Queries with Noisy Comparisons	2015	PODS