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
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,334 | SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization | 2022 | SIGMOD | 4.1945683e-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.0032169493 |
| 386 | Shooting Stars in the Sky: An Online Algorithm for Skyline Queries | 2002 | VLDB | 0.00024768022 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 2,136 | A Generic Approach to Bulk Loading Multidimensional Index Structures | 1997 | VLDB | 9.4721139e-05 |
| 2,500 | Efficient Skyline Computation over Low-Cardinality Domains | 2007 | VLDB | 8.6457563e-05 |
| 4,509 | Privacy Skyline: Privacy with Multidimensional Adversarial Knowledge | 2007 | VLDB | 6.1270304e-05 |
| 5,062 | Randomized Multi-pass Streaming Skyline Algorithms | 2009 | VLDB | 5.7268277e-05 |
| 5,240 | On Finding Skylines in External Memory | 2011 | PODS | 5.6104868e-05 |
| 7,585 | Query Processing Techniques for Multiversion Access Methods | 1996 | VLDB | 4.7037113e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,076 | Window Query-Optimal Clustering of Spatial Objects | 1995 | PODS | 5.223696e-05 |
| 1,502 | Efficient Searching with Linear Constraints (Extended Abstract) | 1998 | PODS | 0.00011643406 |
| 12,105 | Space-Efficient Range Reporting for Categorical Data | 2012 | PODS | 4.1945683e-05 |
| 7,845 | On Top-k Range Reporting in 2D Space | 2015 | PODS | 4.6365341e-05 |
| 5,240 | On Finding Skylines in External Memory | 2011 | PODS | 5.6104868e-05 |
| 2,203 | Independent Range Sampling | 2014 | PODS | 9.2981095e-05 |
| 11,825 | Efficient Top-k Indexing via General Reductions | 2016 | PODS | 4.1945683e-05 |
| 1,182 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013455963 |
| 7,846 | Dynamic Top-K Range Reporting in External Memory | 2012 | PODS | 4.6365341e-05 |
| 11,965 | A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting | 2014 | PODS | 4.1945683e-05 |