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: 4227
Venue: SIGMOD
Year: 2009
Pagerank: 7.9083221e-05
Overall Rank: 2,974 | 79.60%
DOI: 10.1145/1559845.1559929

Incoming Non-self Citations Over Time

Authors

1. Norbert Beckmann (University of Bremen)
2. Bernhard Seeger (University of Marburg)

BibTeX Citation

@inproceedings{beckmann_sigmod09,
        title = {{A Revised R*-tree in Comparison with Related Index Structures}},
        author = {Beckmann, Norbert and Seeger, Bernhard},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559929},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559929},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,840	Effectively Learning Spatial Indices	2020	VLDB	9.6404567e-05
4,482	Overlap Interval Partition Join	2014	SIGMOD	6.6753072e-05
4,751	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	6.5241784e-05
6,749	An Incremental Hausdorff Distance Calculation Algorithm	2011	VLDB	5.7844585e-05
8,200	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.4677285e-05
8,686	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	5.3849387e-05
8,687	MCR-Tree: An Efficient Index for Multi-dimensional Core Search	2024	SIGMOD	5.3849387e-05
9,657	An Experimental Evaluation and Investigation of Waves of Misery in R-trees	2022	VLDB	5.2419252e-05
9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	5.2006273e-05
9,974	PLATON: Top-down R-tree Packing with Learned Partition Policy	2023	SIGMOD	5.1845938e-05
10,252	GraphRTX: Lighting the Way to Scalable Graph Analytics	2026	SIGMOD	5.093636e-05
12,053	K-means Split Revisited: Well-grounded Approach and Experimental Evaluation	2016	SIGMOD	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022537944
299	Shoring Up Persistent Applications	1994	SIGMOD	0.00022084669
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
1,370	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010997795
1,778	The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation	2000	VLDB	9.7769047e-05
1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.5068846e-05
2,227	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.9111106e-05
3,217	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.6314544e-05
3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	7.2750277e-05
5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	6.0859946e-05
6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.9806097e-05
7,681	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	5.5683442e-05
9,233	Indexing Medium-dimensionality Data in Oracle	1999	SIGMOD	5.3017497e-05
9,234	On Optimal Node Splitting for R-trees	1998	VLDB	5.3017497e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,053	K-means Split Revisited: Well-grounded Approach and Experimental Evaluation	2016	SIGMOD
2	1,373	A Model for the Prediction of R-tree Performance	1996	PODS
3	2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD
4	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
5	1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
6	1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB
7	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
8	42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB
9	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
10	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD