DBScholar

Back to papers

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.0019923528
Overall Rank
2 | 99.99%
DOI
10.1145/602259.602266

Incoming Non-self Citations Over Time

Authors

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 384 citing papers.

Rank Citing Paper Year Venue Pagerank
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
34 The Design Of Postgres 1986 SIGMOD 0.00049129967
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045755116
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045319457
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00045027197
48 Weaving Relations for Cache Performance 2001 VLDB 0.00043795812
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040363819
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034847854
99 The Design of the POSTGRES Storage System 1987 VLDB 0.00034019355
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031633451
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003136296
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029048509
194 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025637823
207 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024976482
216 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.00024485637
273 Extensible Query Processing in Starburst 1989 SIGMOD 0.00022498382
278 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022310642
281 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022303081
287 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00022001327
291 Object and File Management in the EXODUS Extensible Database System 1986 VLDB 0.00021940923
336 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020652147
338 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020600264
339 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020561716
358 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020011298
363 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019980483
385 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019456733
418 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00018609134
459 Query Processing in Spatial Network Databases 2003 VLDB 0.00017860573
479 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017623894
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017451091
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016874202
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016599925
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015759877
614 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015563362
648 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015156941
667 The Sequoia 2000 Storage Benchmark 1993 SIGMOD 0.00014983804
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014769852
695 Algorithms for Mining Distance-Based Outliers in Large Datasets 1998 VLDB 0.00014696154
744 Client-Server Paradise 1994 VLDB 0.00014305129
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014239937
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013744009
816 Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998 VLDB 0.00013686255
829 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.0001360545
839 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.0001354488
917 Trajectory Clustering: A Partition-and-Group Framework 2007 SIGMOD 0.00013085176
918 Accelerating XPath Location Steps 2002 SIGMOD 0.00013078274
926 On Indexing Mobile Objects 1999 PODS 0.00013041631
967 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012803465
994 Spatial Hash-Joins 1996 SIGMOD 0.00012630797
Previous Page 1 / 8 Next

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.00081200096
113 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00032158942
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,422 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,862 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
5 7,908 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS
6 3,254 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,053 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
10 44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB