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,336 | SLAM: Efficient Sweep Line Algorithms for Kernel Density Visualization | 2022 | SIGMOD | 4.1905499e-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.0032118946 |
| 386 | Shooting Stars in the Sky: An Online Algorithm for Skyline Queries | 2002 | VLDB | 0.00024740283 |
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |
| 2,139 | A Generic Approach to Bulk Loading Multidimensional Index Structures | 1997 | VLDB | 9.4618572e-05 |
| 2,502 | Efficient Skyline Computation over Low-Cardinality Domains | 2007 | VLDB | 8.631993e-05 |
| 4,512 | Privacy Skyline: Privacy with Multidimensional Adversarial Knowledge | 2007 | VLDB | 6.1188233e-05 |
| 5,068 | Randomized Multi-pass Streaming Skyline Algorithms | 2009 | VLDB | 5.7143436e-05 |
| 5,320 | On Finding Skylines in External Memory | 2011 | PODS | 5.5677544e-05 |
| 7,601 | Query Processing Techniques for Multiversion Access Methods | 1996 | VLDB | 4.6967949e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,073 | Window Query-Optimal Clustering of Spatial Objects | 1995 | PODS | 5.2215154e-05 |
| 1,499 | Efficient Searching with Linear Constraints (Extended Abstract) | 1998 | PODS | 0.00011643887 |
| 12,113 | Space-Efficient Range Reporting for Categorical Data | 2012 | PODS | 4.1905499e-05 |
| 7,850 | On Top-k Range Reporting in 2D Space | 2015 | PODS | 4.6320876e-05 |
| 5,320 | On Finding Skylines in External Memory | 2011 | PODS | 5.5677544e-05 |
| 2,207 | Independent Range Sampling | 2014 | PODS | 9.2896559e-05 |
| 11,833 | Efficient Top-k Indexing via General Reductions | 2016 | PODS | 4.1905499e-05 |
| 1,183 | On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) | 1999 | PODS | 0.00013444058 |
| 7,851 | Dynamic Top-K Range Reporting in External Memory | 2012 | PODS | 4.6320876e-05 |
| 11,973 | A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting | 2014 | PODS | 4.1905499e-05 |