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.001992968
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
1,956 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.3169059e-05
2,016 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1771614e-05
2,021 Distributed Trajectory Similarity Search 2017 VLDB 9.1719539e-05
2,064 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.0942902e-05
2,079 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.0775779e-05
2,113 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.0196806e-05
2,149 The Time Index: An Access Structure for Temporal Data 1990 VLDB 8.9552337e-05
2,162 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.935022e-05
2,179 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 8.9120272e-05
2,205 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 8.8556449e-05
2,263 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.7304715e-05
2,265 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.7238222e-05
2,294 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.6837534e-05
2,309 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.6626683e-05
2,319 Hardware Acceleration for Spatial Selections and Joins 2003 SIGMOD 8.6460188e-05
2,358 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5817166e-05
2,367 Capacity Constrained Assignment in Spatial Databases 2008 SIGMOD 8.5623448e-05
2,388 Parallel R-trees 1992 SIGMOD 8.5375939e-05
2,421 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.4897323e-05
2,448 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4494625e-05
2,542 A Predicate Matching Algorithm for Database Rule Systems 1990 SIGMOD 8.3237167e-05
2,556 Architecture and Implementation of the Darmstadt Database Kernel System 1987 SIGMOD 8.3026469e-05
2,560 Extensible Buffer Management of Indexes 1992 VLDB 8.2993451e-05
2,561 Answering Top-k Queries Using Views 2006 VLDB 8.2977193e-05
2,588 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.2518251e-05
2,706 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 8.1111109e-05
2,783 Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search 2024 SIGMOD 8.0242863e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.967335e-05
2,828 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 7.9650643e-05
2,847 Transaction Time Indexing with Version Compression 2008 VLDB 7.9447157e-05
2,858 A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data 2013 VLDB 7.9354625e-05
2,871 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.9229231e-05
2,872 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.9228762e-05
2,893 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 7.9019071e-05
2,911 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 7.8720638e-05
2,944 Spatio-Textual Similarity Joins 2013 VLDB 7.828107e-05
2,969 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.8000797e-05
3,016 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7483267e-05
3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7330662e-05
3,045 Spatial Keyword Query Processing: An Experimental Evaluation 2013 VLDB 7.72015e-05
3,057 Dynamic Density Based Clustering 2017 SIGMOD 7.6965352e-05
3,099 The DEDALE System for Complex Spatial Queries 1998 SIGMOD 7.6508573e-05
3,108 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.640323e-05
3,111 High-Concurrency Locking in R-Trees 1995 VLDB 7.6374094e-05
3,120 Size Separation Spatial Join 1997 SIGMOD 7.6300049e-05
3,150 Efficient Spatial Sampling of Large Geographical Tables 2012 SIGMOD 7.5916819e-05
3,192 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5512396e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,255 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4890984e-05
3,295 Lightning Fast and Space Efficient Inequality Joins 2015 VLDB 7.448168e-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.0008122792
113 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00032170066
Previous Page 1 / 1 Next

Semantically Similar Papers

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