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: 2233
Venue: SIGMOD
Year: 1984
Pagerank: 0.0032169493
Overall Rank: 2 | 99.99%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Antonin Guttman

Incoming Citations (Sorted by Pagerank)

Showing 50 of 379 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.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
26	The Design Of The Postgres Storage System	1987	VLDB	0.00082378685
44	The Design Of Postgres	1986	SIGMOD	0.00071838587
47	Nearest Neighbor Queries	1995	SIGMOD	0.0007015885
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065631356
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
80	Weaving Relations for Cache Performance	2001	VLDB	0.00055721729
91	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.0005181666
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
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
187	Object and File Management in the EXODUS Extensible Database System	1986	VLDB	0.00036020812
195	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00035406558
231	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00032163466
242	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00031110894
243	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00031074984
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
307	Extensible Query Processing in Starburst	1989	SIGMOD	0.00028211308
343	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00026768139
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
368	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.000254931
389	Query Processing in Spatial Network Databases	2003	VLDB	0.00024620268
400	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002427237
465	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00022455702
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
601	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00019375875
605	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.000193396
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
668	The Sequoia 2000 Storage Benchmark	1993	SIGMOD	0.00018430721
699	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00018015254
736	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00017447617
769	Client-Server Paradise	1994	VLDB	0.00016918508
774	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016865771
823	Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method	1998	VLDB	0.000162378
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
949	Tioga: Providing Data Management Support for Scientific Visualization Applications	1993	VLDB	0.00015111638
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

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.0018397217
19	Interval Hierarchies And Their Application To Predicate Files	1977	SIGMOD	0.00091625014

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,541	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.5795657e-05
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
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05
7,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05
3,275	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2897998e-05
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065631356
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538