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
1,038 Redundancy in Spatial Databases 1989 SIGMOD 0.00012349149
1,091 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.0001205609
1,098 A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series 2013 VLDB 0.00012016918
1,106 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00011960288
1,132 Qd-tree: Learning Data Layouts for Big Data Analytics 2020 SIGMOD 0.00011873466
1,143 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011810737
1,183 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011589152
1,235 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00011384515
1,241 Processing Queries By Linear Constraints 1997 PODS 0.00011373551
1,286 Automatic Optimization for MapReduce Programs 2011 VLDB 0.00011187304
1,311 Continuous Nearest Neighbor Search 2002 VLDB 0.00011063629
1,395 Finding Time Period-Based Most Frequent Path in Big Trajectory Data 2013 SIGMOD 0.00010777052
1,411 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00010729946
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
1,419 A Demonstration of SciDB: A Science-Oriented DBMS 2009 VLDB 0.00010704914
1,421 A Data Management Extension Architecture 1987 SIGMOD 0.000107023
1,445 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010607118
1,468 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00010540751
1,480 Efficient Processing of Top-k Spatial Preference Queries 2011 VLDB 0.00010511472
1,514 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010391649
1,524 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.0001033427
1,527 On the Analysis of Indexing Schemes 1997 PODS 0.00010326893
1,549 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010257684
1,554 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010236406
1,574 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010164216
1,594 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010103178
1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.00010045437
1,628 Efficient Processing of Joins on Set-valued Attributes 2003 SIGMOD 0.00010020209
1,642 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 9.9812004e-05
1,648 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 9.9739132e-05
1,649 Relaxing Join and Selection Queries 2006 VLDB 9.9699016e-05
1,660 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 9.9414118e-05
1,661 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9409992e-05
1,662 Indexing Land Surface for Efficient kNN Query 2008 VLDB 9.9409992e-05
1,725 Spreadsheets in RDBMS for OLAP 2003 SIGMOD 9.7733128e-05
1,729 Closest Pair Queries in Spatial Databases 2000 SIGMOD 9.761101e-05
1,738 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.7335994e-05
1,741 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.7287344e-05
1,786 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 9.6344047e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,825 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5443954e-05
1,867 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4581343e-05
1,869 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4516156e-05
1,881 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 9.4262036e-05
1,882 Storage Management in AsterixDB 2014 VLDB 9.4243119e-05
1,884 Effectively Learning Spatial Indices 2020 VLDB 9.422145e-05
1,911 Tioga: Providing Data Management Support for Scientific Visualization Applications 1993 VLDB 9.3720964e-05
1,915 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.368237e-05
1,926 Predictable Performance for Unpredictable Workloads 2009 VLDB 9.3500398e-05
1,930 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3453623e-05
Previous Page 2 / 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