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
1,019 Redundancy in Spatial Databases 1989 SIGMOD 0.00012622386
1,084 A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series 2013 VLDB 0.00012256753
1,110 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00012140661
1,129 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00012061727
1,135 Qd-tree: Learning Data Layouts for Big Data Analytics 2020 SIGMOD 0.00012032847
1,139 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.0001202217
1,175 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011812263
1,201 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00011674339
1,219 Processing Queries By Linear Constraints 1997 PODS 0.00011620957
1,257 Automatic Optimization for MapReduce Programs 2011 VLDB 0.000114432
1,281 Continuous Nearest Neighbor Search 2002 VLDB 0.00011349245
1,370 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00010997795
1,373 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001098638
1,376 A Demonstration of SciDB: A Science-Oriented DBMS 2009 VLDB 0.00010973814
1,377 A Data Management Extension Architecture 1987 SIGMOD 0.00010972063
1,381 Finding Time Period-Based Most Frequent Path in Big Trajectory Data 2013 SIGMOD 0.00010965263
1,418 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010835539
1,428 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00010811922
1,441 Efficient Processing of Top-k Spatial Preference Queries 2011 VLDB 0.00010778831
1,512 On the Analysis of Indexing Schemes 1997 PODS 0.00010536001
1,517 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010520118
1,525 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010493702
1,529 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010482997
1,561 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010361147
1,572 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010329197
1,592 Efficient Processing of Joins on Set-valued Attributes 2003 SIGMOD 0.00010253457
1,602 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010239526
1,612 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010218134
1,614 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00010215186
1,618 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00010207737
1,619 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00010207737
1,620 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00010206305
1,636 Relaxing Join and Selection Queries 2006 VLDB 0.00010156479
1,685 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010017073
1,687 Spreadsheets in RDBMS for OLAP 2003 SIGMOD 0.00010005718
1,698 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.980335e-05
1,722 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.9227051e-05
1,742 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 9.8748669e-05
1,776 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.7853414e-05
1,778 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.7769047e-05
1,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.6928497e-05
1,819 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.6810907e-05
1,840 Effectively Learning Spatial Indices 2020 VLDB 9.6404567e-05
1,851 Tioga: Providing Data Management Support for Scientific Visualization Applications 1993 VLDB 9.6139015e-05
1,874 Storage Management in AsterixDB 2014 VLDB 9.5750002e-05
1,877 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.5658249e-05
1,879 Predictable Performance for Unpredictable Workloads 2009 VLDB 9.5613416e-05
1,880 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.5562066e-05
1,901 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.5068846e-05
1,934 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 9.4561907e-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.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