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

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 379 citing papers.

Rank Citing Paper Year Venue Pagerank
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,027 Accelerating XPath Location Steps 2002 SIGMOD 0.0001458865
1,034 Redundancy in Spatial Databases 1989 SIGMOD 0.00014534274
1,114 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00013901031
1,115 Finding Time Period-Based Most Frequent Path in Big Trajectory Data 2013 SIGMOD 0.00013894562
1,126 Trajectory Clustering: A Partition-and-Group Framework 2007 SIGMOD 0.00013821443
1,157 A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series 2013 VLDB 0.00013610658
1,165 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00013557822
1,172 Processing Queries By Linear Constraints 1997 PODS 0.00013505441
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013486418
1,182 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013455963
1,184 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 0.00013455208
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013406526
1,239 A Demonstration of SciDB: A Science-Oriented DBMS 2009 VLDB 0.00013102195
1,275 Continuous Nearest Neighbor Search 2002 VLDB 0.00012883899
1,280 Automatic Optimization for MapReduce Programs 2011 VLDB 0.0001285503
1,339 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00012492597
1,398 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00012197586
1,403 Efficient Processing of Top-k Spatial Preference Queries 2011 VLDB 0.00012176993
1,435 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00012004456
1,437 A Data Management Extension Architecture 1987 SIGMOD 0.00011981662
1,479 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00011749057
1,488 On the Analysis of Indexing Schemes 1997 PODS 0.00011699446
1,502 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643406
1,513 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00011593275
1,514 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00011593275
1,528 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011497734
1,549 Spreadsheets in RDBMS for OLAP 2003 SIGMOD 0.00011428835
1,576 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00011286717
1,611 Qd-tree: Learning Data Layouts for Big Data Analytics 2020 SIGMOD 0.00011147324
1,631 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00011078269
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010669106
1,763 Efficient Processing of Joins on Set-valued Attributes 2003 SIGMOD 0.00010638276
1,768 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010622873
1,774 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 0.00010604097
1,776 Distributed Trajectory Similarity Search 2017 VLDB 0.00010593716
1,806 Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces 2000 VLDB 0.00010490769
1,811 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010467197
1,830 Relaxing Join and Selection Queries 2006 VLDB 0.000103862
1,876 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 0.00010239284
1,917 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 0.0001009778
1,925 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 0.00010073407
1,933 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010038508
1,971 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 9.893198e-05
1,983 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.8638201e-05
1,997 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 9.8322994e-05
2,013 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7928688e-05
2,021 Storage Management in AsterixDB 2014 VLDB 9.7601304e-05
2,030 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7378136e-05
2,041 Indexable PLA for Efficient Similarity Search 2007 VLDB 9.6992894e-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.0018397217
19 Interval Hierarchies And Their Application To Predicate Files 1977 SIGMOD 0.00091625014
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,541 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.5795657e-05
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
2,030 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7378136e-05
7,729 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6660821e-05
3,275 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2897998e-05
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065631356
9,767 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2856106e-05
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538