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
- 4166
- Venue
- SIGMOD
- Year
- 2009
- Pagerank
- 7.3101573e-05
- Overall Rank
- 3,259 | 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,676 |
Effectively Learning Spatial Indices |
2020 |
VLDB |
8.326321e-05 |
| 5,197 |
Overlap Interval Partition Join |
2014 |
SIGMOD |
5.6308314e-05 |
| 5,463 |
The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data |
2023 |
SIGMOD |
5.4920768e-05 |
| 6,802 |
An Incremental Hausdorff Distance Calculation Algorithm |
2011 |
VLDB |
4.9172931e-05 |
| 8,354 |
Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing |
2023 |
VLDB |
4.5329424e-05 |
| 8,470 |
Rapidash: Efficient Detection of Constraint Violations |
2024 |
VLDB |
4.4993203e-05 |
| 9,484 |
MCR-Tree: An Efficient Index for Multi-dimensional Core Search |
2024 |
SIGMOD |
4.3300131e-05 |
| 9,532 |
An Experimental Evaluation and Investigation of Waves of Misery in R-trees |
2022 |
VLDB |
4.3232695e-05 |
| 9,769 |
Adaptive Indexing of Objects with Spatial Extent |
2023 |
VLDB |
4.2815042e-05 |
| 9,826 |
PLATON: Top-down R-tree Packing with Learned Partition Policy |
2023 |
SIGMOD |
4.2710095e-05 |
| 11,860 |
K-means Split Revisited: Well-grounded Approach and Experimental Evaluation |
2016 |
SIGMOD |
4.1905499e-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.0032118946 |
| 6 |
The R*-tree: An Efficient and Robust Access Method for Points and Rectangles |
1990 |
SIGMOD |
0.0016113151 |
| 129 |
The X-tree: An Index Structure for High-Dimensional Data |
1996 |
VLDB |
0.00044255276 |
| 242 |
Generalized Search Trees for Database Systems (Extended Abstract) |
1995 |
VLDB |
0.00031093647 |
| 292 |
Shoring Up Persistent Applications |
1994 |
SIGMOD |
0.00028735468 |
| 301 |
The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries |
1997 |
SIGMOD |
0.00028396714 |
| 356 |
Hilbert R-tree: An Improved R-tree Using Fractals |
1994 |
VLDB |
0.00026091196 |
| 1,111 |
Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension |
1994 |
PODS |
0.0001389881 |
| 1,476 |
Towards an Analysis of Range Query Performance in Spatial Data Structures |
1993 |
PODS |
0.00011752931 |
| 1,923 |
The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation |
2000 |
VLDB |
0.00010079134 |
| 2,139 |
A Generic Approach to Bulk Loading Multidimensional Index Structures |
1997 |
VLDB |
9.4618572e-05 |
| 2,519 |
Concurrency and Recovery in Generalized Search Trees |
1997 |
SIGMOD |
8.6048934e-05 |
| 3,278 |
Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data |
2002 |
SIGMOD |
7.2858181e-05 |
| 3,653 |
The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree |
2004 |
SIGMOD |
6.8725114e-05 |
| 5,864 |
Benchmarking Spatial Join Operations with Spatial Output |
1995 |
VLDB |
5.2947135e-05 |
| 6,073 |
Window Query-Optimal Clustering of Spatial Objects |
1995 |
PODS |
5.2215154e-05 |
| 7,653 |
Efficient Concurrency Control in Multidimensional Access Methods |
1999 |
SIGMOD |
4.6831774e-05 |
| 9,020 |
Indexing Medium-dimensionality Data in Oracle |
1999 |
SIGMOD |
4.4049428e-05 |
| 9,021 |
On Optimal Node Splitting for R-trees |
1998 |
VLDB |
4.4049428e-05 |
Semantically Similar Papers