Back to papers
A Revised R*-tree in Comparison with Related Index Structures
Summary: DBMS-friendly redesign of the R*-tree with single-path insertions and subtree choice. Experiments show faster tree creation and ~30% I/O gains for 2D/3D, with larger gains in higher dimensions; drawbacks include re-insertion, limited overlap optimization, and balance issues.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 4165
- Venue
- SIGMOD
- Year
- 2009
- Pagerank
- 7.3160522e-05
- Overall Rank
- 3,255 | 77.36%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 2,678 |
Effectively Learning Spatial Indices |
2020 |
VLDB |
8.3252088e-05 |
| 5,190 |
Overlap Interval Partition Join |
2014 |
SIGMOD |
5.6381091e-05 |
| 5,572 |
The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data |
2023 |
SIGMOD |
5.4277273e-05 |
| 6,770 |
An Incremental Hausdorff Distance Calculation Algorithm |
2011 |
VLDB |
4.9317829e-05 |
| 8,359 |
Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing |
2023 |
VLDB |
4.5372925e-05 |
| 8,472 |
Rapidash: Efficient Detection of Constraint Violations |
2024 |
VLDB |
4.5036378e-05 |
| 9,482 |
MCR-Tree: An Efficient Index for Multi-dimensional Core Search |
2024 |
SIGMOD |
4.3341665e-05 |
| 9,531 |
An Experimental Evaluation and Investigation of Waves of Misery in R-trees |
2022 |
VLDB |
4.3274164e-05 |
| 9,767 |
Adaptive Indexing of Objects with Spatial Extent |
2023 |
VLDB |
4.2856106e-05 |
| 9,827 |
PLATON: Top-down R-tree Packing with Learned Partition Policy |
2023 |
SIGMOD |
4.2751057e-05 |
| 11,852 |
K-means Split Revisited: Well-grounded Approach and Experimental Evaluation |
2016 |
SIGMOD |
4.1945683e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 19 of 19 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 |
| 129 |
The X-tree: An Index Structure for High-Dimensional Data |
1996 |
VLDB |
0.0004429571 |
| 242 |
Generalized Search Trees for Database Systems (Extended Abstract) |
1995 |
VLDB |
0.00031110894 |
| 284 |
The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries |
1997 |
SIGMOD |
0.00028994728 |
| 292 |
Shoring Up Persistent Applications |
1994 |
SIGMOD |
0.00028741386 |
| 354 |
Hilbert R-tree: An Improved R-tree Using Fractals |
1994 |
VLDB |
0.00026137988 |
| 1,114 |
Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension |
1994 |
PODS |
0.00013901031 |
| 1,479 |
Towards an Analysis of Range Query Performance in Spatial Data Structures |
1993 |
PODS |
0.00011749057 |
| 1,925 |
The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation |
2000 |
VLDB |
0.00010073407 |
| 2,136 |
A Generic Approach to Bulk Loading Multidimensional Index Structures |
1997 |
VLDB |
9.4721139e-05 |
| 2,516 |
Concurrency and Recovery in Generalized Search Trees |
1997 |
SIGMOD |
8.6106981e-05 |
| 3,275 |
Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data |
2002 |
SIGMOD |
7.2897998e-05 |
| 3,650 |
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree |
2004 |
SIGMOD |
6.8783391e-05 |
| 5,860 |
Benchmarking Spatial Join Operations with Spatial Output |
1995 |
VLDB |
5.2990241e-05 |
| 6,076 |
Window Query-Optimal Clustering of Spatial Objects |
1995 |
PODS |
5.223696e-05 |
| 7,651 |
Efficient Concurrency Control in Multidimensional Access Methods |
1999 |
SIGMOD |
4.6876337e-05 |
| 9,017 |
Indexing Medium-dimensionality Data in Oracle |
1999 |
SIGMOD |
4.4091374e-05 |
| 9,018 |
On Optimal Node Splitting for R-trees |
1998 |
VLDB |
4.4091374e-05 |
Semantically Similar Papers