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
5,483 DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows 2022 SIGMOD 6.2019677e-05
5,517 Scalable Ranked Publish/Subscribe 2008 VLDB 6.1889819e-05
5,565 Efficient Allocation Algorithms for OLAP over Imprecise Data 2006 VLDB 6.171506e-05
5,638 An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees 1998 SIGMOD 6.138684e-05
5,653 UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search 2025 VLDB 6.1332953e-05
5,664 FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data 2008 VLDB 6.1289238e-05
5,666 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 6.1285141e-05
5,692 Spatial Independent Range Sampling 2021 SIGMOD 6.119196e-05
5,709 GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons 2018 VLDB 6.1142154e-05
5,740 A Benchmark for Evaluating Moving Object Indexes 2008 VLDB 6.1035012e-05
5,768 An Example of Knowledge-Based Query Processing in a CAD/CAM DBMS 1984 VLDB 6.0945305e-05
5,795 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 6.0859946e-05
5,800 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 6.0850924e-05
5,838 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 6.0702428e-05
5,857 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 6.0644613e-05
5,875 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0564961e-05
5,887 Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference 2010 SIGMOD 6.0500409e-05
5,888 Clustering Techniques for Minimizing External Path Length 1996 VLDB 6.0498293e-05
5,894 Ganos: A Multidimensional, Dynamic, and Scene-Oriented Cloud-Native Spatial Database Engine 2022 VLDB 6.0486927e-05
5,895 The 3W Model and Algebra for Unified Data Mining 2000 VLDB 6.0486927e-05
5,912 Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data 1995 PODS 6.0442093e-05
6,016 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 6.0082425e-05
6,025 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 6.002739e-05
6,045 Helios: Hyperscale Indexing for the Cloud & Edge 2020 VLDB 5.9957544e-05
6,052 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.9941393e-05
6,089 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.9806097e-05
6,093 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.978635e-05
6,133 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 5.9654376e-05
6,179 Densely Connected User Community and Location Cluster Search in Location-Based Social Networks 2020 SIGMOD 5.9496108e-05
6,217 Clue-based Spatio-textual Query 2017 VLDB 5.9425753e-05
6,251 The Flexible Socio Spatial Group Queries 2019 VLDB 5.9415675e-05
6,285 Trajectory Similarity Join in Spatial Networks 2017 VLDB 5.9270112e-05
6,289 External Memory Algorithms 1998 PODS 5.9261616e-05
6,298 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.9227722e-05
6,404 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.8859287e-05
6,426 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.8809448e-05
6,429 Just-In-Time Data Structures 2015 CIDR 5.8805678e-05
6,451 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.8751993e-05
6,459 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.8727182e-05
6,491 Two-dimensional Substring Indexing 2001 PODS 5.8641664e-05
6,537 Range Search over Encrypted Multi-Attribute Data 2023 VLDB 5.8478276e-05
6,561 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8389373e-05
6,615 A Topology-Aware Localized Update Strategy for Graph-Based ANN Index 2026 VLDB 5.8214312e-05
6,646 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.8148791e-05
6,647 AGILE: Adaptive Indexing for Context-Aware Information Filters 2005 SIGMOD 5.8147547e-05
6,669 Spatial Joins in Main Memory: Implementation Matters! 2015 VLDB 5.8077717e-05
6,670 Replicated Layout for In-Memory Database Systems 2022 VLDB 5.8074043e-05
6,715 Walking Through A Very Large Virtual Environment In Real-time 2001 VLDB 5.7959545e-05
6,749 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.7844585e-05
6,777 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.7773009e-05
Previous Page 5 / 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