I/O-Efficient Planar Range Skyline and Attrition Priority Queues
Summary: I/O-optimal linear-space solutions for planar range skyline: static top-open queries solved optimally across continuous, grid and rank-space models; left-open/4-sided queries require Ω((n/B)^ε + k/B) I/Os—matching orthogonal range reporting so skyline adds no extra hardness. Also the first dynamic linear-space structure supporting top-open queries in O(log_{2B^ε} n + k/B^{1-ε}) I/Os with O(log_{2B^ε} n) updates, built atop a new I/O-efficient catenable priority queue with attrition. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Casper Kejlberg-Rasmussen (Aarhus University)
- 2. Yufei Tao (Chinese University of Hong Kong; Korea Advanced Institute of Science and Technology)
- 3. Konstantinos Tsakalidis (Hong Kong University of Science and Technology)
- 4. Kostas Tsichlas (Aristotle University of Thessaloniki)
- 5. Jeonghun Yoon (Korea Advanced Institute of Science and Technology)
BibTeX Citation
@inproceedings{kejlbergrasmussen_pods13,
address = {New York, NY, USA},
series = {{PODS} '13},
title = {{I/O-Efficient Planar Range Skyline and Attrition Priority Queues}},
url = {https://dl.acm.org/doi/10.1145/2463664.2465225},
doi = {10.1145/2463664.2465225},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Kejlberg-Rasmussen, Casper and Tao, Yufei and Tsakalidis, Konstantinos and Tsichlas, Kostas and Yoon, Jeonghun},
year = {2013}
}
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,533 | SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization | 2022 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2 | R-Trees: A Dynamic Index Structure For Spatial Searching | 1984 | SIGMOD | 0.0020210012 |
| 308 | Shooting Stars in the Sky: An Online Algorithm for Skyline Queries | 2002 | VLDB | 0.00021787597 |
| 1,529 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00010482997 |
| 1,901 | A Generic Approach to Bulk Loading Multidimensional Index Structures | 1997 | VLDB | 9.5068846e-05 |
| 2,434 | Efficient Skyline Computation over Low-Cardinality Domains | 2007 | VLDB | 8.5839844e-05 |
| 4,037 | Privacy Skyline: Privacy with Multidimensional Adversarial Knowledge | 2007 | VLDB | 6.9431497e-05 |
| 4,941 | Randomized Multi-pass Streaming Skyline Algorithms | 2009 | VLDB | 6.4333573e-05 |
| 5,016 | On Finding Skylines in External Memory | 2011 | PODS | 6.3998091e-05 |
| 7,595 | Query Processing Techniques for Multiversion Access Methods | 1996 | VLDB | 5.5888857e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,089 | Window Query-Optimal Clustering of Spatial Objects | 1995 | PODS |
| 2 | 1,561 | Efficient Searching with Linear Constraints (Extended Abstract) | 1998 | PODS |
| 3 | 12,302 | Space-Efficient Range Reporting for Categorical Data | 2012 | PODS |
| 4 | 8,172 | On Top-k Range Reporting in 2D Space | 2015 | PODS |
| 5 | 5,016 | On Finding Skylines in External Memory | 2011 | PODS |
| 6 | 2,443 | Independent Range Sampling | 2014 | PODS |
| 7 | 12,028 | Efficient Top-k Indexing via General Reductions | 2016 | PODS |
| 8 | 1,529 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS |
| 9 | 8,173 | Dynamic Top-K Range Reporting in External Memory | 2012 | PODS |
| 10 | 12,163 | A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting | 2014 | PODS |