R-Trees: A Dynamic Index Structure For Spatial Searching

Summary: R-tree, a dynamic index for multidimensional spatial data; supports non-zero sized objects with bounding rectangles. Algorithms for search and update; empirical tests show strong performance and applicability to modern spatial DBs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2234
Venue: SIGMOD
Year: 1984
Pagerank: 0.0032118946
Overall Rank: 2 | 99.99%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Antonin Guttman

Incoming Citations (Sorted by Pagerank)

Showing 50 of 380 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
26	The Design Of The Postgres Storage System	1987	VLDB	0.00082350905
44	The Design Of Postgres	1986	SIGMOD	0.00071946446
48	Nearest Neighbor Queries	1995	SIGMOD	0.0006954126
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256
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
80	Weaving Relations for Cache Performance	2001	VLDB	0.00055735291
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00051785122
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
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
187	Object and File Management in the EXODUS Extensible Database System	1986	VLDB	0.00035990623
195	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00035317524
231	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00032141918
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031093647
243	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00031052437
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
309	Extensible Query Processing in Starburst	1989	SIGMOD	0.00028195213
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026756534
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
367	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00025518228
391	Query Processing in Spatial Network Databases	2003	VLDB	0.00024560891
399	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00024359304
464	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00022476798
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
579	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.0001982328
595	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019459302
665	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00018437125
667	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00018431008
696	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00017991162
730	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00017443615
766	Client-Server Paradise	1994	VLDB	0.0001690298
768	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016864875
820	Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method	1998	VLDB	0.00016232743
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
951	Tioga: Providing Data Management Support for Scientific Visualization Applications	1993	VLDB	0.00015099037
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

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
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018380955
19	Interval Hierarchies And Their Application To Predicate Files	1977	SIGMOD	0.00091479494

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,558	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5441554e-05
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
2,033	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7315522e-05
7,727	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6616221e-05
3,278	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2858181e-05
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888