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
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051134355
34 The Design Of Postgres 1986 SIGMOD 0.00049063803
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045609336
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044967652
48 Weaving Relations for Cache Performance 2001 VLDB 0.00043770511
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0004024707
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
101 The Design of the POSTGRES Storage System 1987 VLDB 0.00033939695
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031562001
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031291457
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.000289618
198 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025558119
210 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024910589
216 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.00024446892
275 Extensible Query Processing in Starburst 1989 SIGMOD 0.000224395
281 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.00022262975
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
289 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00021955394
297 Object and File Management in the EXODUS Extensible Database System 1986 VLDB 0.0002187415
325 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020930941
338 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.0002058961
339 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020558018
361 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00019948113
363 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019931086
386 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019396455
419 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00018558415
463 Query Processing in Spatial Network Databases 2003 VLDB 0.00017806376
481 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017567157
490 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017397036
530 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016832286
547 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016545689
598 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015711108
616 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015512487
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
668 The Sequoia 2000 Storage Benchmark 1993 SIGMOD 0.00014936842
687 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014736766
698 Algorithms for Mining Distance-Based Outliers in Large Datasets 1998 VLDB 0.0001465073
747 Client-Server Paradise 1994 VLDB 0.00014259869
760 Partition Based Spatial-Merge Join 1996 SIGMOD 0.0001419395
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013710393
818 Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998 VLDB 0.00013657405
832 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013562724
843 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013501136
920 Trajectory Clustering: A Partition-and-Group Framework 2007 SIGMOD 0.00013041987
922 Accelerating XPath Location Steps 2002 SIGMOD 0.0001303574
930 On Indexing Mobile Objects 1999 PODS 0.00013000067
968 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012763144
999 Spatial Hash-Joins 1996 SIGMOD 0.00012590189
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.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