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
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
34 The Design Of Postgres 1986 SIGMOD 0.00049302774
41 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00046675394
42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00046170812
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
49 Weaving Relations for Cache Performance 2001 VLDB 0.00043781096
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040719947
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
99 The Design of the POSTGRES Storage System 1987 VLDB 0.00034506601
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.0003221055
118 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031922279
145 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029548428
190 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00026105472
202 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00025454884
227 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.00023958508
268 Extensible Query Processing in Starburst 1989 SIGMOD 0.00022788687
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
283 Object and File Management in the EXODUS Extensible Database System 1986 VLDB 0.00022377907
287 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022323585
293 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00022259273
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
350 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020425134
354 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00020355578
369 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00019945234
371 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019869565
406 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00019054532
407 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00019021441
449 Query Processing in Spatial Network Databases 2003 VLDB 0.0001826404
468 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017986163
483 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017756569
522 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00017133516
546 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016734556
592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00016029789
601 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015870156
650 The Sequoia 2000 Storage Benchmark 1993 SIGMOD 0.00015319951
675 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00015080025
693 Algorithms for Mining Distance-Based Outliers in Large Datasets 1998 VLDB 0.00014918477
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
726 Client-Server Paradise 1994 VLDB 0.0001460632
728 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014542772
797 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013927251
807 Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998 VLDB 0.00013884448
810 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013874464
815 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013835761
893 Accelerating XPath Location Steps 2002 SIGMOD 0.00013374715
896 On Indexing Mobile Objects 1999 PODS 0.0001334014
918 Trajectory Clustering: A Partition-and-Group Framework 2007 SIGMOD 0.00013215285
936 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00013092484
994 Spatial Hash-Joins 1996 SIGMOD 0.00012764684
Previous Page 1 / 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