Database Paper Browser

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
2234
Venue
SIGMOD
Year
1984
Pagerank
0.0032118946
Overall Rank
2 | 99.99%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 380 citing papers.

Rank Citing Paper Year Venue Pagerank
1,028 Accelerating XPath Location Steps 2002 SIGMOD 0.00014578947
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00014524981
1,111 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.0001389881
1,118 Finding Time Period-Based Most Frequent Path in Big Trajectory Data 2013 SIGMOD 0.00013851562
1,127 Trajectory Clustering: A Partition-and-Group Framework 2007 SIGMOD 0.00013801775
1,156 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00013606064
1,157 A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series 2013 VLDB 0.00013600695
1,171 Processing Queries By Linear Constraints 1997 PODS 0.00013507216
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058
1,184 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 0.00013442644
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013404419
1,241 A Demonstration of SciDB: A Science-Oriented DBMS 2009 VLDB 0.00013089816
1,272 Continuous Nearest Neighbor Search 2002 VLDB 0.00012871443
1,281 Automatic Optimization for MapReduce Programs 2011 VLDB 0.00012837411
1,301 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00012702767
1,317 Efficient Processing of Top-k Spatial Preference Queries 2011 VLDB 0.00012615781
1,326 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00012571381
1,399 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00012197728
1,436 A Data Management Extension Architecture 1987 SIGMOD 0.00011978473
1,476 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00011752931
1,485 On the Analysis of Indexing Schemes 1997 PODS 0.00011698762
1,499 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643887
1,511 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00011582099
1,512 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00011582099
1,519 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011535609
1,547 Spreadsheets in RDBMS for OLAP 2003 SIGMOD 0.00011417795
1,580 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00011272266
1,605 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00011180126
1,608 Qd-tree: Learning Data Layouts for Big Data Analytics 2020 SIGMOD 0.00011169837
1,749 Distributed Trajectory Similarity Search 2017 VLDB 0.00010684148
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010661725
1,757 Efficient Processing of Joins on Set-valued Attributes 2003 SIGMOD 0.00010659352
1,766 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010611043
1,769 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010608375
1,802 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.0001048177
1,808 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010476269
1,830 Relaxing Join and Selection Queries 2006 VLDB 0.0001037611
1,878 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 0.00010229691
1,916 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 0.00010110473
1,923 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010079134
1,924 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010075677
1,966 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 9.9130791e-05
1,987 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.8561164e-05
2,001 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8275076e-05
2,018 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7852268e-05
2,020 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.7766925e-05
2,024 Storage Management in AsterixDB 2014 VLDB 9.7528344e-05
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05
2,045 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.6950855e-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
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018380955
19 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00091479494
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,558 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.5441554e-05
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05
7,727 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6616221e-05
3,278 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2858181e-05
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065500256
9,769 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2815042e-05
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888