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.001992968
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 384 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.0011405675
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
34 The Design Of Postgres 1986 SIGMOD 0.00049142315
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045773967
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045337853
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
48 Weaving Relations for Cache Performance 2001 VLDB 0.00043805923
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
99 The Design of the POSTGRES Storage System 1987 VLDB 0.00034033763
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031645463
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003137356
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029061754
193 Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases 2001 SIGMOD 0.00025648171
206 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024986675
216 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.00024485024
273 Extensible Query Processing in Starburst 1989 SIGMOD 0.00022504729
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
280 Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search 2007 VLDB 0.0002230467
287 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00021970198
291 Object and File Management in the EXODUS Extensible Database System 1986 VLDB 0.00021951101
335 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020660268
338 Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting 2012 SIGMOD 0.00020585187
341 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00020539791
358 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00020019939
364 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019976696
385 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.0001946565
418 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00018617842
458 Query Processing in Spatial Network Databases 2003 VLDB 0.00017868943
478 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017631293
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017457851
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016880616
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016607433
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015766567
613 Exact Indexing of Dynamic Time Warping 2002 VLDB 0.00015570505
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015149775
665 The Sequoia 2000 Storage Benchmark 1993 SIGMOD 0.00014990574
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014775707
695 Algorithms for Mining Distance-Based Outliers in Large Datasets 1998 VLDB 0.00014702685
743 Client-Server Paradise 1994 VLDB 0.00014311524
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014246504
811 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013745617
815 Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method 1998 VLDB 0.00013689839
829 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013611445
837 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013551047
917 Trajectory Clustering: A Partition-and-Group Framework 2007 SIGMOD 0.00013091246
918 Accelerating XPath Location Steps 2002 SIGMOD 0.00013084437
926 On Indexing Mobile Objects 1999 PODS 0.00013047723
965 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012809362
994 Spatial Hash-Joins 1996 SIGMOD 0.00012636707
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.0008122792
113 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00032170066
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,421 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,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
5 7,904 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS
6 3,253 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,048 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
10 44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB