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
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

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
1,978 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.3627341e-05
2,010 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 9.3085202e-05
2,020 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.2983514e-05
2,046 Distributed Trajectory Similarity Search 2017 VLDB 9.260657e-05
2,101 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.1657486e-05
2,115 The Time Index: An Access Structure for Temporal Data 1990 VLDB 9.1449719e-05
2,127 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.127762e-05
2,135 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.1133971e-05
2,158 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.0622995e-05
2,168 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.0469646e-05
2,227 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.9111106e-05
2,249 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.8700017e-05
2,254 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.8603695e-05
2,283 Hardware Acceleration for Spatial Selections and Joins 2003 SIGMOD 8.8099424e-05
2,310 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.7650894e-05
2,327 Capacity Constrained Assignment in Spatial Databases 2008 SIGMOD 8.7476945e-05
2,341 Parallel R-trees 1992 SIGMOD 8.7233426e-05
2,375 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.6753909e-05
2,495 A Predicate Matching Algorithm for Database Rule Systems 1990 SIGMOD 8.5034389e-05
2,518 Architecture and Implementation of the Darmstadt Database Kernel System 1987 SIGMOD 8.4755514e-05
2,525 Answering Top-k Queries Using Views 2006 VLDB 8.4653166e-05
2,534 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.4561875e-05
2,548 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.432498e-05
2,572 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4027322e-05
2,590 Extensible Buffer Management of Indexes 1992 VLDB 8.3696843e-05
2,648 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 8.2957097e-05
2,774 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 8.1372328e-05
2,776 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 8.1356669e-05
2,794 A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data 2013 VLDB 8.1167671e-05
2,824 Transaction Time Indexing with Version Compression 2008 VLDB 8.0882727e-05
2,827 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 8.0831263e-05
2,853 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 8.0383547e-05
2,974 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.9083221e-05
2,979 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.8984588e-05
2,989 Spatial Keyword Query Processing: An Experimental Evaluation 2013 VLDB 7.8896275e-05
3,020 Dynamic Density Based Clustering 2017 SIGMOD 7.8445412e-05
3,037 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.8275859e-05
3,041 Spatio-Textual Similarity Joins 2013 VLDB 7.8254399e-05
3,043 The DEDALE System for Complex Spatial Queries 1998 SIGMOD 7.8228924e-05
3,047 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.8155543e-05
3,057 High-Concurrency Locking in R-Trees 1995 VLDB 7.807389e-05
3,066 Size Separation Spatial Join 1997 SIGMOD 7.7941163e-05
3,094 Efficient Spatial Sampling of Large Geographical Tables 2012 SIGMOD 7.765466e-05
3,139 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.7188328e-05
3,193 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.649474e-05
3,217 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.6314544e-05
3,240 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.6071649e-05
3,252 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.5951443e-05
3,279 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.5711218e-05
3,290 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.5531472e-05
Previous Page 3 / 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.00082404462
113 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00032684992
Previous Page 1 / 1 Next

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