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: 2497
Venue: SIGMOD
Year: 1990
Pagerank: 0.0016113151
Overall Rank: 6 | 99.97%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 279 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00061977022
78	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00056385781
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00044255276
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
171	Fuzzy Queries in Multimedia Database Systems	1998	PODS	0.00038843975
195	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00035317524
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031093647
263	OPTICS: Ordering Points To Identify the Clustering Structure	1999	SIGMOD	0.00029955858
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028845557
301	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00028396714
340	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026854084
356	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026091196
362	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00025758421
386	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00024740283
391	Query Processing in Spatial Network Databases	2003	VLDB	0.00024560891
471	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00022348285
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
537	Fast Time Sequence Indexing for Arbitrary L_p Norms	2000	VLDB	0.00020650291
574	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD	0.0001987713
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
602	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00019350521
628	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018957327
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018437125
675	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018304179
697	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017964755
746	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017212135
766	Client-Server Paradise	1994	VLDB	0.0001690298
821	Dimensionality Reduction for Similarity Searching in Dynamic Databases	1998	SIGMOD	0.00016232579
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
862	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00015798065
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
929	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.0001523035
985	An Efficient and Scalable Approach to CNN Queries in a Road Network	2005	VLDB	0.00014834799
986	Managing Intervals Efficiently in Object-Relational Databases	2000	VLDB	0.00014825631
999	Similarity-Based Queries for Time Series Data	1997	SIGMOD	0.00014726031
1,004	On Indexing Mobile Objects	1999	PODS	0.00014694512
1,013	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014632051
1,055	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00014391376
1,060	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00014359912
1,111	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.0001389881
1,156	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00013606064
1,171	Processing Queries By Linear Constraints	1997	PODS	0.00013507216
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
1,180	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS	0.00013455619
1,184	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	0.00013442644
1,199	Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce	2013	VLDB	0.00013358019
1,262	Efficient Query Processing in Geographic Web Search Engines	2006	SIGMOD	0.00012982825

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.0032118946
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
7,046	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	4.8471584e-05
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
3,653	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8725114e-05
1,519	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011535609
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
2,033	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7315522e-05