The R*-tree: An Efficient and Robust Access Method for Points and Rectangles

Summary: R*-tree: joint optimization of area, margin, and overlap in inner nodes for rectangles and multidimensional points. Extensive experiments on a standardized testbed show it outperforms Guttman’s linear/quadratic R-trees and Greene’s variant across point/rectangle queries and map overlay, with efficient data support and only modest implementation cost. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2496
Venue: SIGMOD
Year: 1990
Pagerank: 0.0016162015
Overall Rank: 6 | 99.97%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 278 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00062029383
79	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056242144
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
169	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00038895438
195	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00035406558
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031110894
270	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029505642
284	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028994728
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028919734
341	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026810548
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
362	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00025770385
386	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00024768022
389	Query Processing in Spatial Network Databases	2003	VLDB	0.00024620268
471	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00022364776
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
539	Fast Time Sequence Indexing for Arbitrary L_p Norms	2000	VLDB	0.00020666392
575	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.00019882723
599	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00019394214
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
648	Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects	2009	VLDB	0.00018666267
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018451109
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
701	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017938417
749	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017228334
769	Client-Server Paradise	1994	VLDB	0.00016918508
825	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016228517
838	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016088938
871	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00015767786
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
931	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00015238406
983	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00014860126
986	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00014838568
997	Similarity-Based Queries for Time Series Data	1997	SIGMOD	0.00014739219
1,002	On Indexing Mobile Objects	1999	PODS	0.00014702555
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
1,061	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00014368716
1,067	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00014327945
1,114	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00013901031
1,165	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00013557822
1,172	Processing Queries By Linear Constraints	1997	PODS	0.00013505441
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
1,183	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455596
1,184	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	0.00013455208
1,220	Efficient Query Processing in Geographic Web Search Engines	2006	SIGMOD	0.00013223504

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065631356

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
838	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016088938
7,054	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	4.8496866e-05
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
3,650	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8783391e-05
1,528	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011497734
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05