On Optimal Node Splitting for R-trees
Summary: Polynomial-time optimal bipartition for R-tree node splits; valid for any objective depending only on bounding rectangles, O(n^d) (d>1). Experiments show 5-15% query-time gains over heuristics, implying near-optimality of current splits; with a global overflow-insertion strategy, gains up to 120% over the standard. (summarized by gpt-5-nano 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 |
|---|---|---|---|---|
| 3,255 | A Revised R*-tree in Comparison with Related Index Structures | 2009 | SIGMOD | 7.3160522e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 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 |
| 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 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,528 | A Model for the Prediction of R-tree Performance | 1996 | PODS | 0.00011497734 |
| 11,852 | K-means Split Revisited: Well-grounded Approach and Experimental Evaluation | 2016 | SIGMOD | 4.1945683e-05 |
| 6 | The R*-tree: An Efficient and Robust Access Method for Points and Rectangles | 1990 | SIGMOD | 0.0016162015 |
| 354 | Hilbert R-tree: An Improved R-tree Using Fractals | 1994 | VLDB | 0.00026137988 |
| 2,030 | Analysis Of Object Oriented Spatial Access Methods | 1987 | SIGMOD | 9.7378136e-05 |
| 148 | Efficient Processing of Spatial Joins Using R-trees | 1993 | SIGMOD | 0.00041182766 |
| 3,650 | The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree | 2004 | SIGMOD | 6.8783391e-05 |
| 7,054 | Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability | 2018 | VLDB | 4.8496866e-05 |
| 7,519 | A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing | 2005 | VLDB | 4.7180617e-05 |
| 3,255 | A Revised R*-tree in Comparison with Related Index Structures | 2009 | SIGMOD | 7.3160522e-05 |