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.2656699e-05
Overall Rank: 5,091 | 65.88%
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,151	On Finding Skylines in External Memory	2011	PODS	6.2376472e-05
8,213	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.3607592e-05
8,501	Skyline Operator on Anti-correlated Distributions	2013	VLDB	5.3131213e-05
8,941	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.2361195e-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.00036097627
258	Efficient Progressive Skyline Computation	2001	VLDB	0.00022896896
317	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021232519
1,126	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011888563
2,499	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.3611036e-05
2,573	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD	8.2576057e-05
5,565	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	6.0652619e-05
8,682	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.2738178e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,573	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD
2	2,499	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
3	12,804	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
4	4,279	Relative Error Streaming Quantiles	2021	PODS
5	3,487	Approaching the Skyline in Z Order	2007	VLDB
6	5,606	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
7	5,151	On Finding Skylines in External Memory	2011	PODS
8	9,541	Computing All Skyline Probabilities for Uncertain Data	2009	PODS
9	6,770	Categorical Skylines for Streaming Data	2008	SIGMOD
10	10,245	Skyline Queries with Noisy Comparisons	2015	PODS