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
9,034 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.3274671e-05
9,068 Efficient Secure and Verifiable Location-Based Skyline Queries over Encrypted Data 2022 VLDB 5.3251649e-05
9,099 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.3250598e-05
9,104 Spatial Priority Search: An Access Technique for Scaleless Maps 1991 SIGMOD 5.3245105e-05
9,165 Dimensional Testing for Reverse k-Nearest Neighbor Search 2017 VLDB 5.3101672e-05
9,233 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 5.3017497e-05
9,234 On Optimal Node Splitting for R-trees 1998 VLDB 5.3017497e-05
9,254 Boosting Moving Object Indexing through Velocity Partitioning 2012 VLDB 5.297624e-05
9,319 TrafficDB: HERE’s High Performance Shared-Memory Data Store 2016 VLDB 5.289545e-05
9,324 Main-Memory Operation Buffering for Efficient R-Tree Update 2007 VLDB 5.289545e-05
9,334 Adaptive Indexing in High-Dimensional Metric Spaces 2023 VLDB 5.2884486e-05
9,343 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.2854091e-05
9,365 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.279561e-05
9,400 PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads 2019 VLDB 5.2755515e-05
9,417 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.2740525e-05
9,544 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2528121e-05
9,657 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.2419252e-05
9,871 Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs 2024 SIGMOD 5.2043672e-05
9,887 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.2006273e-05
9,970 NEXT: A New Secondary Index Framework for LSM-based Data Storage 2025 SIGMOD 5.1845938e-05
9,974 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.1845938e-05
10,015 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.17669e-05
10,052 Top-k Relevant Semantic Place Retrieval on Spatial RDF Data 2016 SIGMOD 5.1685424e-05
10,124 Raster is Faster: Rethinking Ray Tracing in Database Indexing 2026 CIDR 5.093636e-05
10,209 CMANNS: GPU-Accelerated Graph Index Construction for ANNS via Compute-Memory Disaggregation 2026 SIGMOD 5.093636e-05
10,528 Effective Durable Community Search in Large Temporal Graph 2026 VLDB 5.093636e-05
10,569 Toward Drift-Aware Database Benchmarking 2026 VLDB 5.093636e-05
10,629 MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance 2026 VLDB 5.093636e-05
10,672 Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve 2025 SIGMOD 5.093636e-05
10,674 Parallel kd-tree with Batch Updates 2025 SIGMOD 5.093636e-05
10,824 Efficient Concurrent Updates to Persistent Randomized Binary Search Trees 2025 VLDB 5.093636e-05
10,945 The Accuracy of Cardinality Estimators: Unraveling the Evaluation Result Conundrum 2025 VLDB 5.093636e-05
10,984 Benchmarking Adaptive Multidimensional Indices 2025 VLDB 5.093636e-05
11,193 BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data 2024 SIGMOD 5.093636e-05
11,199 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 5.093636e-05
11,334 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 5.093636e-05
11,341 TUCKET: A Tensor Time Series Data Structure for Efficient and Accurate Factor Analysis over Time Ranges 2024 VLDB 5.093636e-05
11,392 ST4ML: Machine Learning Oriented Spatio-Temporal Data Processing at Scale 2023 SIGMOD 5.093636e-05
11,413 SH2O: Efficient Data Access for Work-Sharing Databases 2023 SIGMOD 5.093636e-05
11,534 Faster and Better Solution to Embed Lp Metrics by Tree Metrics 2022 SIGMOD 5.093636e-05
11,559 Approximate Range Thresholding 2022 SIGMOD 5.093636e-05
11,565 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 5.093636e-05
11,577 Fast Dataset Search with Earth Mover's Distance 2022 VLDB 5.093636e-05
11,702 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 5.093636e-05
11,738 Fast Algorithm for Anchor Graph Hashing 2021 VLDB 5.093636e-05
11,844 Interactive Visualization for Big Spatial Data 2019 SIGMOD 5.093636e-05
11,853 Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation 2019 SIGMOD 5.093636e-05
11,979 Query Processing Techniques for Big Spatial-Keyword Data 2017 SIGMOD 5.093636e-05
12,018 Efficient Mining of Regional Movement Patterns in Semantic Trajectories 2017 VLDB 5.093636e-05
12,053 K-means Split Revisited: Well-grounded Approach and Experimental Evaluation 2016 SIGMOD 5.093636e-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.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