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
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00012393393
1,095 A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series 2013 VLDB 0.00012050625
1,107 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00011993663
1,128 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.00011905274
1,132 Qd-tree: Learning Data Layouts for Big Data Analytics 2020 SIGMOD 0.00011898257
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011848523
1,178 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011632691
1,227 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.000114264
1,237 Processing Queries By Linear Constraints 1997 PODS 0.00011396286
1,281 Automatic Optimization for MapReduce Programs 2011 VLDB 0.00011213384
1,304 Continuous Nearest Neighbor Search 2002 VLDB 0.00011104243
1,389 Finding Time Period-Based Most Frequent Path in Big Trajectory Data 2013 SIGMOD 0.00010817927
1,404 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00010767648
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001076417
1,408 A Demonstration of SciDB: A Science-Oriented DBMS 2009 VLDB 0.00010743556
1,411 A Data Management Extension Architecture 1987 SIGMOD 0.00010741047
1,446 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010629222
1,464 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00010580339
1,477 Efficient Processing of Top-k Spatial Preference Queries 2011 VLDB 0.00010551239
1,527 On the Analysis of Indexing Schemes 1997 PODS 0.00010350889
1,530 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010344205
1,546 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010294163
1,552 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010275036
1,559 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010252232
1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010201796
1,589 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010139591
1,618 Efficient Processing of Joins on Set-valued Attributes 2003 SIGMOD 0.00010056773
1,625 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.0001004502
1,634 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.0001001862
1,641 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00010007832
1,643 Relaxing Join and Selection Queries 2006 VLDB 0.00010006399
1,650 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 9.9787032e-05
1,651 Indexing Land Surface for Efficient kNN Query 2008 VLDB 9.9787032e-05
1,652 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 9.9778734e-05
1,714 Spreadsheets in RDBMS for OLAP 2003 SIGMOD 9.80996e-05
1,719 Closest Pair Queries in Spatial Databases 2000 SIGMOD 9.7976056e-05
1,730 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.7654336e-05
1,731 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.7639519e-05
1,774 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 9.6688719e-05
1,793 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.6235776e-05
1,813 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5801503e-05
1,856 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4938262e-05
1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4871409e-05
1,875 Storage Management in AsterixDB 2014 VLDB 9.4576907e-05
1,878 Effectively Learning Spatial Indices 2020 VLDB 9.4451309e-05
1,897 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 9.4092345e-05
1,899 Tioga: Providing Data Management Support for Scientific Visualization Applications 1993 VLDB 9.4070548e-05
1,903 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.4032472e-05
1,918 Predictable Performance for Unpredictable Workloads 2009 VLDB 9.3789552e-05
1,922 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3751198e-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.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