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: h52759c68d03cd902
Venue: SIGMOD
Year: 1984
Pagerank: 0.0019892478
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 385 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,819	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB	5.658433e-05
6,864	Walking Through A Very Large Virtual Environment In Real-time	2001	VLDB	5.6451897e-05
6,924	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.6292653e-05
6,941	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.6229105e-05
6,962	Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing	2000	PODS	5.6181217e-05
6,992	Global Immutable Region Computation	2014	SIGMOD	5.609582e-05
7,013	Towards a Spatial Query Language: User Interface Considerations	1988	VLDB	5.6045961e-05
7,045	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	5.5975731e-05
7,125	DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation	2022	VLDB	5.580601e-05
7,187	Operation Specific Locking In B-Trees	1987	PODS	5.5744874e-05
7,209	Location-Aware Pub/Sub System: When Continuous Moving Queries Meet Dynamic Event Streams	2015	SIGMOD	5.5695569e-05
7,236	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.5629185e-05
7,306	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	5.5452852e-05
7,324	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.5387994e-05
7,456	Cracking Vector Search Indexes	2025	VLDB	5.5083275e-05
7,469	DEX: Query Execution in a Delta-based Storage System	2017	SIGMOD	5.50341e-05
7,474	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	5.5026548e-05
7,477	The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	5.5022037e-05
7,519	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	5.4892692e-05
7,563	Scaling and Time Warping in Time Series Querying	2005	VLDB	5.478063e-05
7,742	Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges	2017	SIGMOD	5.4468611e-05
7,754	Query Processing Techniques for Multiversion Access Methods	1996	VLDB	5.443551e-05
7,811	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.432001e-05
7,876	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	5.4194298e-05
7,924	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.4090777e-05
8,132	A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing	2005	VLDB	5.3739121e-05
8,247	The HV-tree: a Memory Hierarchy Aware Version Index	2010	VLDB	5.3548467e-05
8,267	Indexing Mixed Types for Approximate Retrieval	2005	VLDB	5.3492332e-05
8,302	Cubrick: Indexing Millions of Records per Second for Interactive Analytics	2016	VLDB	5.3430752e-05
8,322	Managing Complex Objects in an Extensible Relational DBMS	1989	VLDB	5.3398181e-05
8,391	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.3248747e-05
8,402	On Nearest Neighbor Indexing of Nonlinear Trajectories	2003	PODS	5.3233293e-05
8,637	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD	5.2829747e-05
8,683	THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads	2015	SIGMOD	5.2733366e-05
8,773	LIT: Lightning-fast In-memory Temporal Indexing	2024	SIGMOD	5.2682366e-05
8,783	Maintenance of Spatial Semijoin Queries on Moving Points	2004	VLDB	5.2645572e-05
8,813	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	5.2570736e-05
8,829	SwiftSpatial: Spatial Joins on Modern Hardware	2025	SIGMOD	5.2533436e-05
8,834	Incremental Partitioning for Efficient Spatial Data Analytics	2022	VLDB	5.2524856e-05
8,847	Spatial Queries with Two kNN Predicates	2012	VLDB	5.2495672e-05
8,865	MCR-Tree: An Efficient Index for Multi-dimensional Core Search	2024	SIGMOD	5.2471429e-05
8,877	The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index	2014	SIGMOD	5.2450451e-05
8,881	Rapidash: Efficient Detection of Constraint Violations	2024	VLDB	5.2442249e-05
8,883	Adaptive Index Structures	2002	VLDB	5.2436823e-05
8,924	FINEX: A Fast Index for Exact & Flexible Density-Based Clustering	2023	SIGMOD	5.2361195e-05
8,941	I/O-Efficient Planar Range Skyline and Attrition Priority Queues	2013	PODS	5.2361195e-05
8,978	HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle	2022	SIGMOD	5.2334381e-05
8,990	The Impact of Global Clustering on Spatial Database Systems	1994	VLDB	5.2300111e-05
9,023	Constraint-Based Query Optimization for Spatial Databases	1991	PODS	5.2216313e-05
9,080	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD	5.2106452e-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.00081207565
113	Interval Hierarchies And Their Application To Predicate Files	1977	SIGMOD	0.00032096323

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,436	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB
2	90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB
3	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
4	1,869	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
5	7,924	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
6	3,267	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	10,085	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
10	44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB