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.2566665e-05
Overall Rank: 5,144 | 65.42%
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,318	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	7.4324312e-05
8,479	Skyline Operator on Anti-correlated Distributions	2013	VLDB	5.3332727e-05
8,811	Finding Pareto Optimal Groups: Group-based Skyline	2015	VLDB	5.2723238e-05
8,913	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.2559789e-05
11,842	SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization	2022	SIGMOD	4.9793485e-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
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021311041
817	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013672764
2,491	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.3921786e-05
5,070	Randomized Multi-pass Streaming Skyline Algorithms	2009	VLDB	6.2890477e-05

Semantically Similar Papers

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