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
5,492 GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons 2018 VLDB 6.0966695e-05
5,526 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 6.0804398e-05
5,537 VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries 2010 VLDB 6.075858e-05
5,547 GORDER: An Efficient Method for KNN Join Processing 2004 VLDB 6.0715188e-05
5,554 AQWA: Adaptive Query-Workload-Aware Partitioning of Big Spatial Data 2015 VLDB 6.0707181e-05
5,595 Database Support for Knowledge-Based Image Evaluation 1987 VLDB 6.0547483e-05
5,625 DenForest: Enabling Fast Deletion in Incremental Density-Based Clustering over Sliding Windows 2022 SIGMOD 6.0454405e-05
5,633 A Topology-Aware Localized Update Strategy for Graph-Based ANN Index 2026 VLDB 6.039647e-05
5,668 Scalable Ranked Publish/Subscribe 2008 VLDB 6.0272577e-05
5,708 Efficient Allocation Algorithms for OLAP over Imprecise Data 2006 VLDB 6.0107692e-05
5,729 An Alternative Storage Organization for ROLAP Aggregate Views Based on Cubetrees 1998 SIGMOD 5.9975458e-05
5,814 Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search 2015 PODS 5.9684385e-05
5,835 Spatial Independent Range Sampling 2021 SIGMOD 5.9606673e-05
5,878 A Benchmark for Evaluating Moving Object Indexes 2008 VLDB 5.9442479e-05
5,891 ARKGraph: All-Range Approximate K-Nearest-Neighbor Graph 2023 VLDB 5.9396547e-05
5,904 An Example of Knowledge-Based Query Processing in a CAD/CAM DBMS 1984 VLDB 5.9352837e-05
5,921 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.9284908e-05
5,970 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.9116326e-05
5,977 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9106575e-05
6,020 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.8934229e-05
6,024 Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference 2010 SIGMOD 5.8919629e-05
6,033 Ganos: A Multidimensional, Dynamic, and Scene-Oriented Cloud-Native Spatial Database Engine 2022 VLDB 5.8906344e-05
6,034 The 3W Model and Algebra for Unified Data Mining 2000 VLDB 5.8906344e-05
6,050 Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data 1995 PODS 5.8865586e-05
6,076 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.8774917e-05
6,116 Trajectory Similarity Join in Spatial Networks 2017 VLDB 5.8657138e-05
6,123 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8633884e-05
6,146 Dynamic Range-Filtering Approximate Nearest Neighbor Search 2025 VLDB 5.8561603e-05
6,162 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 5.8512412e-05
6,165 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.8501981e-05
6,189 Helios: Hyperscale Indexing for the Cloud & Edge 2020 VLDB 5.8391363e-05
6,191 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.8388106e-05
6,231 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.8255825e-05
6,256 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 5.8162066e-05
6,261 The Flexible Socio Spatial Group Queries 2019 VLDB 5.8143328e-05
6,316 Densely Connected User Community and Location Cluster Search in Location-Based Social Networks 2020 SIGMOD 5.7968726e-05
6,360 Clue-based Spatio-textual Query 2017 VLDB 5.78729e-05
6,427 External Memory Algorithms 1998 PODS 5.7713075e-05
6,431 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.7688769e-05
6,466 Just-In-Time Data Structures 2015 CIDR 5.7588551e-05
6,552 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.7306642e-05
6,597 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.7220175e-05
6,604 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.7196547e-05
6,631 Two-dimensional Substring Indexing 2001 PODS 5.7114931e-05
6,680 Range Search over Encrypted Multi-Attribute Data 2023 VLDB 5.6950181e-05
6,730 Replicated Layout for In-Memory Database Systems 2022 VLDB 5.6801409e-05
6,756 Trajectory Similarity Measurement: An Efficiency Perspective 2024 VLDB 5.6724628e-05
6,760 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.6706378e-05
6,798 AGILE: Adaptive Indexing for Context-Aware Information Filters 2005 SIGMOD 5.6629605e-05
6,811 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.6598101e-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.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