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: 1540
Venue: PODS
Year: 2011
Pagerank: 6.3998091e-05
Overall Rank: 5,016 | 65.59%
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,254	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.5928992e-05
8,312	Skyline Operator on Anti-correlated Distributions	2013	VLDB	5.4556836e-05
8,645	Finding Pareto Optimal Groups: Group-based Skyline	2015	VLDB	5.3933023e-05
8,750	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.3766157e-05
11,533	SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization	2022	SIGMOD	5.093636e-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
308	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021787597
792	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013979615
2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.5839844e-05
4,941	Randomized Multi-pass Streaming Skyline Algorithms	2009	VLDB	6.4333573e-05

Semantically Similar Papers

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