The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
Summary: Introduces the Priority R-tree (PR-tree), the first R-tree variant that guarantees worst-case optimal window-query I/Os: O((N/B)^(1-1/d) + T/B). Establishes asymptotic optimality and demonstrates practical gains over existing R-trees, excelling on extreme data via extensive real and synthetic experiments. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Lars Arge
- 2. Mark de Berg
- 3. Herman J. Haverkort
- 4. Ke Yi
Incoming Citations (Sorted by Pagerank)
Showing 9 of 9 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,876 | ArrayStore: A Storage Manager for Complex Parallel Array Processing | 2011 | SIGMOD | 0.00010239284 |
| 3,255 | A Revised R*-tree in Comparison with Related Index Structures | 2009 | SIGMOD | 7.3160522e-05 |
| 4,780 | TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning | 2013 | SIGMOD | 5.9263494e-05 |
| 6,424 | Range Search over Encrypted Multi-Attribute Data | 2023 | VLDB | 5.0670573e-05 |
| 7,772 | K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization | 2007 | VLDB | 4.6554316e-05 |
| 8,359 | Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing | 2023 | VLDB | 4.5372925e-05 |
| 12,131 | Measuring Two-Event Structural Correlations on Graphs | 2012 | VLDB | 4.1945683e-05 |
| 12,294 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1945683e-05 |
| 12,497 | Efficient Query Processing on Unstructured Tetrahedral Meshes | 2006 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 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 |
| 5 | The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes | 1981 | SIGMOD | 0.0018397217 |
| 6 | The R*-tree: An Efficient and Robust Access Method for Points and Rectangles | 1990 | SIGMOD | 0.0016162015 |
| 24 | The R+-Tree: A Dynamic Index For Multi-Dimensional Objects | 1987 | VLDB | 0.00083378538 |
| 56 | Direct Spatial Search on Pictorial Databases Using Packed R-trees | 1985 | SIGMOD | 0.00065631356 |
| 354 | Hilbert R-tree: An Improved R-tree Using Fractals | 1994 | VLDB | 0.00026137988 |
| 769 | Client-Server Paradise | 1994 | VLDB | 0.00016918508 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 12,411 | Towards Efficient Main-Memory Use For Optimum Tree Index Update | 2008 | VLDB | 4.1945683e-05 |
| 1,067 | The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries | 2003 | VLDB | 0.00014327945 |
| 3,255 | A Revised R*-tree in Comparison with Related Index Structures | 2009 | SIGMOD | 7.3160522e-05 |
| 1,528 | A Model for the Prediction of R-tree Performance | 1996 | PODS | 0.00011497734 |
| 2,246 | Parallel R-trees | 1992 | SIGMOD | 9.2075292e-05 |
| 2,030 | Analysis Of Object Oriented Spatial Access Methods | 1987 | SIGMOD | 9.7378136e-05 |
| 9,018 | On Optimal Node Splitting for R-trees | 1998 | VLDB | 4.4091374e-05 |
| 12,294 | Worst-Case Efficient Range Search Indexing | 2009 | PODS | 4.1945683e-05 |
| 6 | The R*-tree: An Efficient and Robust Access Method for Points and Rectangles | 1990 | SIGMOD | 0.0016162015 |
| 7,054 | Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability | 2018 | VLDB | 4.8496866e-05 |