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: 2295
Venue: SIGMOD
Year: 1984
Pagerank: 0.0020210012
Overall Rank: 2 | 99.99%
DOI: 10.1145/602259.602266

Incoming Non-self Citations Over Time

Authors

1. Antonin Guttman (University of California Berkeley)

BibTeX Citation

@inproceedings{guttman_sigmod84,
        title = {{R-TREES: A DYNAMIC INDEX STRUCTURE FOR SPATIAL SEARCHING}},
        author = {Guttman, Antonin},
        series = {{SIGMOD} '84},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/602259.602266},
        url = {https://dl.acm.org/doi/10.1145/602259.602266},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 381 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,830	Global Immutable Region Computation	2014	SIGMOD	5.759977e-05
6,849	Towards a Spatial Query Language: User Interface Considerations	1988	VLDB	5.7547607e-05
6,887	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	5.7457967e-05
6,894	Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing	2000	PODS	5.744549e-05
6,953	Trajectory Similarity Measurement: An Efficiency Perspective	2024	VLDB	5.7303405e-05
6,960	DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation	2022	VLDB	5.7303405e-05
7,026	Operation Specific Locking In B-Trees	1987	PODS	5.7232444e-05
7,042	Location-Aware Pub/Sub System: When Continuous Moving Queries Meet Dynamic Event Streams	2015	SIGMOD	5.7189999e-05
7,070	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.7116663e-05
7,124	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.6961208e-05
7,140	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	5.6928705e-05
7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.6873519e-05
7,300	DEX: Query Execution in a Delta-based Storage System	2017	SIGMOD	5.6509215e-05
7,305	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	5.6501646e-05
7,310	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.6494751e-05
7,350	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	5.6358517e-05
7,402	Scaling and Time Warping in Time Series Querying	2005	VLDB	5.6250511e-05
7,426	Dynamic Range-Filtering Approximate Nearest Neighbor Search	2025	VLDB	5.6211019e-05
7,474	GTS: GPU-based Tree Index for Fast Similarity Search	2024	SIGMOD	5.6093517e-05
7,576	Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges	2017	SIGMOD	5.593012e-05
7,595	Query Processing Techniques for Multiversion Access Methods	1996	VLDB	5.5888857e-05
7,632	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.5777517e-05
7,708	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	5.5628618e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05
7,939	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	5.5181056e-05
8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	5.492543e-05
8,123	Managing Complex Objects in an Extensible Relational DBMS	1989	VLDB	5.4830239e-05
8,200	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.4677285e-05
8,202	Cubrick: Indexing Millions of Records per Second for Interactive Analytics	2016	VLDB	5.4672903e-05
8,207	The HV-tree: a Memory Hierarchy Aware Version Index	2010	VLDB	5.4666057e-05
8,210	On Nearest Neighbor Indexing of Nonlinear Trajectories	2003	PODS	5.4661361e-05
8,442	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD	5.4246876e-05
8,499	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.4133616e-05
8,575	LIT: Lightning-fast In-memory Temporal Indexing	2024	SIGMOD	5.4095946e-05
8,593	Maintenance of Spatial Semijoin Queries on Moving Points	2004	VLDB	5.4055214e-05
8,644	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	5.3934068e-05
8,659	Spatial Queries with Two kNN Predicates	2012	VLDB	5.3904242e-05
8,680	The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index	2014	SIGMOD	5.3857754e-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
8,689	Adaptive Index Structures	2002	VLDB	5.3843737e-05
8,733	FINEX: A Fast Index for Exact & Flexible Density-Based Clustering	2023	SIGMOD	5.3766157e-05
8,750	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.3766157e-05
8,791	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	5.3717005e-05
8,796	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.3702721e-05
8,828	Constraint-Based Query Optimization for Spatial Databases	1991	PODS	5.3615981e-05
8,848	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.3577837e-05
8,894	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.3504579e-05
8,898	Cracking Vector Search Indexes	2025	VLDB	5.3495662e-05
8,927	Hyperspace: The Indexing Subsystem of Azure Synapse	2021	VLDB	5.3483178e-05

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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
2	85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB
3	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
4	1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
5	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
6	3,217	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD
7	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
8	116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD
9	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
10	42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB