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 31 of 381 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,056	Range Thresholding on Streams	2016	SIGMOD	5.093636e-05
12,182	An Effective Encoding Scheme for Spatial RDF Data	2014	VLDB	5.093636e-05
12,258	Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects	2013	VLDB	5.093636e-05
12,288	QuEval: Beyond high-dimensional indexing à la carte	2013	VLDB	5.093636e-05
12,303	Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility	2012	PODS	5.093636e-05
12,463	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	5.093636e-05
12,472	Transforming Range Queries To Equivalent Box Queries To Optimize Page Access	2010	VLDB	5.093636e-05
12,489	Worst-Case Efficient Range Search Indexing	2009	PODS	5.093636e-05
12,517	Demonstration of the TrajStore System	2009	VLDB	5.093636e-05
12,605	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	5.093636e-05
12,660	IndeGS: Index Supported Graphics Data Server for CFD Data Postprocessing	2007	VLDB	5.093636e-05
12,672	On Dominating Your Neighborhood Profitably	2007	VLDB	5.093636e-05
12,674	MIST: Distributed Indexing and Querying in Sensor Networks using Statistical Models	2007	VLDB	5.093636e-05
12,675	Early Profile Pruning on XML-aware Publish-Subscribe Systems	2007	VLDB	5.093636e-05
12,688	Meta-data Indexing for XPath Location Steps	2006	SIGMOD	5.093636e-05
12,690	Efficient Query Processing on Unstructured Tetrahedral Meshes	2006	SIGMOD	5.093636e-05
12,704	Using High Dimensional Indexes to Support Relevance Feedback Based Interactive Images Retrieval	2006	VLDB	5.093636e-05
12,714	Indexing for Function Approximation	2006	VLDB	5.093636e-05
12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	5.093636e-05
12,761	Complex Spatio-Temporal Pattern Queries	2005	VLDB	5.093636e-05
12,778	Indexing and Mining Streams	2004	SIGMOD	5.093636e-05
12,794	Efficiency-Quality Tradeoffs for Vector Score Aggregation	2004	VLDB	5.093636e-05
12,818	The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces	2003	VLDB	5.093636e-05
12,821	Improving Performance with Bulk-Inserts in Oracle R-Trees	2003	VLDB	5.093636e-05
12,865	Analyzing Energy Behavior of Spatial Access Methods for Memory-Resident Data	2001	VLDB	5.093636e-05
12,911	GHOST: Fine Granularity Buffering of Index Pages	1999	VLDB	5.093636e-05
12,940	Fast High-Dimensional Data Search in Incomplete Databases	1998	VLDB	5.093636e-05
12,944	Algorithms for Querying by Spatial Structure	1998	VLDB	5.093636e-05
12,950	Multimedia Support for Databases	1997	PODS	5.093636e-05
13,068	Hamming Filter: A Dynamic Signature File Organization for Parallel Stores	1993	VLDB	5.093636e-05
13,197	Panel on Extensible Database Systems	1986	SIGMOD	5.093636e-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