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: 1541
Venue: PODS
Year: 2011
Pagerank: 5.5677544e-05
Overall Rank: 5,320 | 63.03%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Cheng Sheng
2. Yufei Tao

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,608	Skyline Community Search in Multi-valued Networks	2018	SIGMOD	6.9241653e-05
8,652	Finding Pareto Optimal Groups: Group-based Skyline	2015	VLDB	4.4709596e-05
8,761	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4520434e-05
9,506	Skyline Operator on Anti-correlated Distributions	2013	VLDB	4.3300131e-05
11,336	SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization	2022	SIGMOD	4.1905499e-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
386	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00024740283
913	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00015372758
2,502	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.631993e-05
5,068	Randomized Multi-pass Streaming Skyline Algorithms	2009	VLDB	5.7143436e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,141	Approaching the Skyline in Z Order	2007	VLDB	6.4110324e-05
6,680	Categorical Skylines for Streaming Data	2008	SIGMOD	4.960978e-05
3,454	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD	7.0770352e-05
746	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017212135
8,761	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	4.4520434e-05
6,568	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.0020592e-05
262	Efficient Progressive Skyline Computation	2001	VLDB	0.00029962961
913	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00015372758
5,708	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	5.3629476e-05
1,471	Maximal Vector Computation in Large Data Sets	2005	VLDB	0.0001181903