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
5,467 GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons 2018 VLDB 6.119722e-05
5,519 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.0968085e-05
5,526 AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 6.0937354e-05
5,527 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 6.0936219e-05
5,532 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0932822e-05
5,586 Database Support for Knowledge-Based Image Evaluation 1987 VLDB 6.0757421e-05
5,612 DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows 2022 SIGMOD 6.0683695e-05
5,619 A Topology-Aware Localized Update Strategy for Graph-Based ANN Index 2026 VLDB 6.062554e-05
5,655 Scalable Ranked Publish/Subscribe 2008 VLDB 6.0501178e-05
5,695 Efficient Allocation Algorithms for OLAP over Imprecise Data 2006 VLDB 6.0334848e-05
5,714 An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees 1998 SIGMOD 6.0202342e-05
5,796 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 5.9910143e-05
5,819 Spatial Independent Range Sampling 2021 SIGMOD 5.9832748e-05
5,863 A Benchmark for Evaluating Moving Object Indexes 2008 VLDB 5.9667924e-05
5,887 An Example of Knowledge-Based Query Processing in a CAD/CAM DBMS 1984 VLDB 5.9577938e-05
5,905 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.9509027e-05
5,920 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.9475097e-05
5,957 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.93405e-05
5,963 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9330399e-05
6,007 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.9155532e-05
6,012 Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference 2010 SIGMOD 5.9143092e-05
6,019 Ganos: A Multidimensional, Dynamic, and Scene-Oriented Cloud-Native Spatial Database Engine 2022 VLDB 5.9129763e-05
6,020 The 3W Model and Algebra for Unified Data Mining 2000 VLDB 5.9129763e-05
6,035 Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data 1995 PODS 5.9088735e-05
6,097 Trajectory Similarity Join in Spatial Networks 2017 VLDB 5.887961e-05
6,108 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8850424e-05
6,140 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 5.8734337e-05
6,145 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.8717297e-05
6,174 Helios: Hyperscale Indexing for the Cloud & Edge 2020 VLDB 5.8612829e-05
6,176 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.8609559e-05
6,181 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.8595125e-05
6,216 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.847583e-05
6,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 5.8382662e-05
6,263 The Flexible Socio Spatial Group Queries 2019 VLDB 5.8323838e-05
6,313 Densely Connected User Community and Location Cluster Search in Location-Based Social Networks 2020 SIGMOD 5.8165778e-05
6,346 Clue-based Spatio-textual Query 2017 VLDB 5.8092399e-05
6,413 External Memory Algorithms 1998 PODS 5.7931958e-05
6,418 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.7907247e-05
6,452 Just-In-Time Data Structures 2015 CIDR 5.7804153e-05
6,540 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7523628e-05
6,584 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.7436357e-05
6,595 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.7413481e-05
6,616 Two-dimensional Substring Indexing 2001 PODS 5.7330951e-05
6,663 Range Search over Encrypted Multi-Attribute Data 2023 VLDB 5.7166181e-05
6,719 Replicated Layout for In-Memory Database Systems 2022 VLDB 5.6985717e-05
6,730 Trajectory Similarity Measurement: An Efficiency Perspective 2024 VLDB 5.6939772e-05
6,740 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.6916981e-05
6,768 Dynamic Range-Filtering Approximate Nearest Neighbor Search 2025 VLDB 5.686858e-05
6,778 AGILE: Adaptive Indexing for Context-Aware Information Filters 2005 SIGMOD 5.684432e-05
6,790 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.6812765e-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.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