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.0019892478
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 385 citing papers.

Rank Citing Paper Year Venue Pagerank
1,965 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.2829035e-05
2,029 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1470713e-05
2,034 The Time Index: An Access Structure for Temporal Data 1990 VLDB 9.1378213e-05
2,035 Distributed Trajectory Similarity Search 2017 VLDB 9.1372983e-05
2,069 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.0678883e-05
2,076 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.0622765e-05
2,080 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.058838e-05
2,129 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 8.9877592e-05
2,176 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9031141e-05
2,217 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 8.8230488e-05
2,268 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.7144632e-05
2,279 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.6989205e-05
2,307 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.6516423e-05
2,322 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.6301008e-05
2,330 Hardware Acceleration for Spatial Selections and Joins 2003 SIGMOD 8.617839e-05
2,368 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5495935e-05
2,380 Capacity Constrained Assignment in Spatial Databases 2008 SIGMOD 8.5300815e-05
2,400 Parallel R-trees 1992 SIGMOD 8.5059093e-05
2,426 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 8.4692316e-05
2,436 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.4576934e-05
2,537 Extensible Buffer Management of Indexes 1992 VLDB 8.3061306e-05
2,548 A Predicate Matching Algorithm for Database Rule Systems 1990 SIGMOD 8.2927647e-05
2,562 Architecture and Implementation of the Darmstadt Database Kernel System 1987 SIGMOD 8.2723687e-05
2,566 Answering Top-k Queries Using Views 2006 VLDB 8.2679821e-05
2,597 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.2212352e-05
2,717 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 8.0808382e-05
2,791 Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search 2024 SIGMOD 7.9939669e-05
2,818 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 7.9536217e-05
2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9401525e-05
2,857 Transaction Time Indexing with Version Compression 2008 VLDB 7.9152217e-05
2,866 A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data 2013 VLDB 7.9054791e-05
2,879 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.8951769e-05
2,885 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.8929868e-05
2,904 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 7.8723013e-05
2,923 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 7.8423791e-05
2,957 Spatio-Textual Similarity Joins 2013 VLDB 7.799694e-05
2,968 Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring 2020 SIGMOD 7.7879589e-05
3,025 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.7214661e-05
3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7045269e-05
3,054 Spatial Keyword Query Processing: An Experimental Evaluation 2013 VLDB 7.6909799e-05
3,070 Dynamic Density Based Clustering 2017 SIGMOD 7.6675081e-05
3,112 The DEDALE System for Complex Spatial Queries 1998 SIGMOD 7.6224727e-05
3,118 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.6114853e-05
3,121 High-Concurrency Locking in R-Trees 1995 VLDB 7.6094637e-05
3,131 Size Separation Spatial Join 1997 SIGMOD 7.6016052e-05
3,162 Efficient Spatial Sampling of Large Geographical Tables 2012 SIGMOD 7.5630152e-05
3,203 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5227628e-05
3,267 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.46539e-05
3,270 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4613275e-05
3,307 Lightning Fast and Space Efficient Inequality Joins 2015 VLDB 7.4203464e-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.00081207565
113 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00032096323
Previous Page 1 / 1 Next

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