On Finding Skylines in External Memory

Summary: External-memory skyline algorithm for fixed d>=3 with I/O cost O((N/B) log_{M/B}^{d-2}(N/B)), improving the prior in-memory-adapted O((N/B) log_2^{d-2}(N/M)) bound. Tightens dependence on memory/block parameters and generalizes the optimal 2-D external bound. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: he03b500956b8942e
Venue: PODS
Year: 2011
Pagerank: 6.2376472e-05
Overall Rank: 5,151 | 65.48%
DOI: 10.1145/1989284.1989298

Incoming Non-self Citations Over Time

Authors

1. Cheng Sheng (Chinese University of Hong Kong)
2. Yufei Tao (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{sheng_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{On Finding Skylines in External Memory}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989298},
        doi = {10.1145/1989284.1989298},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sheng, Cheng and Tao, Yufei},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,221	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.5060153e-05
8,501	Skyline Operator on Anti-correlated Distributions	2013	VLDB	5.3131213e-05
8,836	Finding Pareto Optimal Groups: Group-based Skyline	2015	VLDB	5.2524026e-05
8,941	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.2361195e-05
11,892	SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization	2022	SIGMOD	4.9605343e-05

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
317	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021232519
820	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013621724
2,499	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.3611036e-05
5,091	Randomized Multi-pass Streaming Skyline Algorithms	2009	VLDB	6.2656699e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,487	Approaching the Skyline in Z Order	2007	VLDB
2	6,770	Categorical Skylines for Streaming Data	2008	SIGMOD
3	3,346	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD
4	640	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD
5	8,941	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS
6	6,609	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD
7	258	Efficient Progressive Skyline Computation	2001	VLDB
8	820	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD
9	5,606	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
10	1,216	Maximal Vector Computation in Large Data Sets	2005	VLDB