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
9,117 Hyperspace: The Indexing Subsystem of Azure Synapse 2021 VLDB 5.208561e-05
9,235 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.1884043e-05
9,279 Efficient Secure and Verifiable Location-Based Skyline Queries over Encrypted Data 2022 VLDB 5.1860131e-05
9,307 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.1859125e-05
9,308 Spatial Priority Search: An Access Technique for Scaleless Maps 1991 SIGMOD 5.1855419e-05
9,364 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.1726938e-05
9,434 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 5.1649835e-05
9,440 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 5.163285e-05
9,441 On Optimal Node Splitting for R-trees 1998 VLDB 5.163285e-05
9,463 Boosting Moving Object Indexing through Velocity Partitioning 2012 VLDB 5.1592099e-05
9,536 TrafficDB: HERE’s High Performance Shared-Memory Data Store 2016 VLDB 5.151324e-05
9,542 Main-Memory Operation Buffering for Efficient R-Tree Update 2007 VLDB 5.151324e-05
9,560 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.1473114e-05
9,579 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.141601e-05
9,616 PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads 2019 VLDB 5.1376962e-05
9,619 Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases 2005 VLDB 5.1376962e-05
9,631 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1362663e-05
9,778 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 5.115551e-05
9,818 NEXT: A New Secondary Index Framework for LSM-based Data Storage 2025 SIGMOD 5.1111219e-05
9,875 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.1049486e-05
10,042 BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data 2024 SIGMOD 5.0786422e-05
10,085 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.0707008e-05
10,100 Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs 2024 SIGMOD 5.068372e-05
10,206 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.0491152e-05
10,243 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.0414736e-05
10,283 Top-k Relevant Semantic Place Retrieval on Spatial RDF Data 2016 SIGMOD 5.0334833e-05
10,378 AITTI: Augmented Interval Tree for Temporal Indexing 2027 SIGMOD 4.9605343e-05
10,427 Raster is Faster: Rethinking Ray Tracing in Database Indexing 2026 CIDR 4.9605343e-05
10,503 CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation 2026 SIGMOD 4.9605343e-05
10,783 Effective Durable Community Search in Large Temporal Graph 2026 VLDB 4.9605343e-05
10,822 Toward Drift-Aware Database Benchmarking 2026 VLDB 4.9605343e-05
10,833 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB 4.9605343e-05
10,940 KAFY: An Extensible and Scalable Transformers-Based System for Trajectory Data Analysis 2026 VLDB 4.9605343e-05
10,976 RayBooster: A Ray Tracing Engine to Accelerate SedonaDB 2026 VLDB 4.9605343e-05
11,145 MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance 2026 VLDB 4.9605343e-05
11,183 Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve 2025 SIGMOD 4.9605343e-05
11,185 Parallel kd-tree with Batch Updates 2025 SIGMOD 4.9605343e-05
11,296 Efficient Concurrent Updates to Persistent Randomized Binary Search Trees 2025 VLDB 4.9605343e-05
11,394 The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum 2025 VLDB 4.9605343e-05
11,424 Benchmarking Adaptive Multidimensional Indices 2025 VLDB 4.9605343e-05
11,596 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.9605343e-05
11,705 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.9605343e-05
11,711 TUCKET: A Tensor Time Series Data Structure for Efficient and Accurate Factor Analysis over Time Ranges 2024 VLDB 4.9605343e-05
11,759 ST4ML: Machine Learning Oriented Spatio-Temporal Data Processing at Scale 2023 SIGMOD 4.9605343e-05
11,777 SH2O: Efficient Data Access for Work-Sharing Databases 2023 SIGMOD 4.9605343e-05
11,893 Faster and Better Solution to Embed Lp Metrics by Tree Metrics 2022 SIGMOD 4.9605343e-05
11,918 Approximate Range Thresholding 2022 SIGMOD 4.9605343e-05
11,924 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 4.9605343e-05
11,935 Fast Dataset Search with Earth Mover's Distance 2022 VLDB 4.9605343e-05
12,091 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 4.9605343e-05
Previous Page 7 / 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