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
6,797 Spatial Joins in Main Memory: Implementation Matters! 2015 VLDB 5.6798855e-05
6,842 Walking Through A Very Large Virtual Environment In Real-time 2001 VLDB 5.6665639e-05
6,905 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.6505668e-05
6,919 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.644237e-05
6,943 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.6380615e-05
6,971 Global Immutable Region Computation 2014 SIGMOD 5.6308579e-05
6,995 Towards a Spatial Query Language: User Interface Considerations 1988 VLDB 5.6258226e-05
7,023 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.6186604e-05
7,100 DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation 2022 VLDB 5.601767e-05
7,164 Operation Specific Locking In B-Trees 1987 PODS 5.5954112e-05
7,189 Location-Aware Pub/Sub System: When Continuous Moving Queries Meet Dynamic Event Streams 2015 SIGMOD 5.590681e-05
7,215 Indexing Methods for Moving Object Databases: Games and Other Applications 2013 SIGMOD 5.5837763e-05
7,289 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.5652691e-05
7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.5598057e-05
7,432 Cracking Vector Search Indexes 2025 VLDB 5.5292193e-05
7,446 DEX: Query Execution in a Delta-based Storage System 2017 SIGMOD 5.5242729e-05
7,452 Strongly Truthful Interactive Regret Minimization 2019 SIGMOD 5.5235226e-05
7,454 The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation 1995 VLDB 5.5230036e-05
7,494 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.5095043e-05
7,541 Scaling and Time Warping in Time Series Querying 2005 VLDB 5.4988401e-05
7,723 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 5.4675199e-05
7,734 Query Processing Techniques for Multiversion Access Methods 1996 VLDB 5.4640143e-05
7,788 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.4526034e-05
7,856 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 5.4399688e-05
7,904 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4295914e-05
8,107 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB 5.3942942e-05
8,222 The HV-tree: a Memory Hierarchy Aware Version Index 2010 VLDB 5.3751545e-05
8,245 Indexing Mixed Types for Approximate Retrieval 2005 VLDB 5.3694945e-05
8,281 Cubrick: Indexing Millions of Records per Second for Interactive Analytics 2016 VLDB 5.3633335e-05
8,301 Managing Complex Objects in an Extensible Relational DBMS 1989 VLDB 5.360065e-05
8,369 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3450708e-05
8,377 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 5.3435192e-05
8,611 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 5.3029766e-05
8,658 THERMAL-JOIN: A Scalable Spatial Join for Dynamic Workloads 2015 SIGMOD 5.2933372e-05
8,743 LIT: Lightning-fast In-memory Temporal Indexing 2024 SIGMOD 5.2882178e-05
8,755 Maintenance of Spatial Semijoin Queries on Moving Points 2004 VLDB 5.2845183e-05
8,786 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 5.2768554e-05
8,804 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2732683e-05
8,809 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2724071e-05
8,820 Spatial Queries with Two kNN Predicates 2012 VLDB 5.2694776e-05
8,845 The PH-Tree – A Space-Efficient Storage Structure and Multi-Dimensional Index 2014 SIGMOD 5.2649359e-05
8,852 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 5.2641151e-05
8,853 MCR-Tree: An Efficient Index for Multi-dimensional Core Search 2024 SIGMOD 5.2641151e-05
8,856 Adaptive Index Structures 2002 VLDB 5.2635701e-05
8,896 FINEX: A Fast Index for Exact & Flexible Density-Based Clustering 2023 SIGMOD 5.2559789e-05
8,913 I/O-Efficient Planar Range Skyline and Attrition Priority Queues 2013 PODS 5.2559789e-05
8,946 HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle 2022 SIGMOD 5.2532874e-05
8,960 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.249844e-05
8,996 Constraint-Based Query Optimization for Spatial Databases 1991 PODS 5.2414297e-05
9,053 Distributed Evaluation of Top-k Temporal Joins 2016 SIGMOD 5.230408e-05
Previous Page 6 / 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