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
2,056 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.6692561e-05
2,088 Capacity Constrained Assignment in Spatial Databases 2008 SIGMOD 9.5707955e-05
2,099 What is the nearest neighbor in high dimensional spaces? 2000 VLDB 9.5429949e-05
2,108 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 9.5283642e-05
2,119 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.5036401e-05
2,139 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.4618572e-05
2,144 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.4375327e-05
2,148 Spatial Keyword Query Processing: An Experimental Evaluation 2013 VLDB 9.4278918e-05
2,151 RINSE: Interactive Data Series Exploration with ADS+ 2015 VLDB 9.4234044e-05
2,232 The DEDALE System for Complex Spatial Queries 1998 SIGMOD 9.2308835e-05
2,245 Parallel R-trees 1992 SIGMOD 9.2048202e-05
2,272 The Time Index: An Access Structure For Temporal Data 1990 VLDB 9.1458869e-05
2,283 Hardware Acceleration for Spatial Selections and Joins 2003 SIGMOD 9.1138663e-05
2,304 A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data 2013 VLDB 9.0659453e-05
2,314 A Predicate Matching Algorithm for Database Rule Systems 1990 SIGMOD 9.0539046e-05
2,371 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 8.9443366e-05
2,372 Predictable Performance for Unpredictable Workloads 2009 VLDB 8.940791e-05
2,434 iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search 2020 VLDB 8.8225986e-05
2,471 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.7158825e-05
2,519 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.6048934e-05
2,532 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.5886308e-05
2,558 Novel Approaches to the Indexing of Moving Object Trajectories 2000 VLDB 8.5441554e-05
2,568 Architecture and Implementation of the Darmstadt Database Kernel System 1987 SIGMOD 8.5205422e-05
2,570 Extensible Buffer Management of Indexes 1992 VLDB 8.5169163e-05
2,592 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 8.4841264e-05
2,673 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3323551e-05
2,676 Effectively Learning Spatial Indices 2020 VLDB 8.326321e-05
2,744 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 8.1917832e-05
2,815 Efficient Spatial Sampling of Large Geographical Tables 2012 SIGMOD 8.0773367e-05
2,905 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9364369e-05
2,936 Answering Top-k Queries Using Views 2006 VLDB 7.8579393e-05
2,969 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 7.7955562e-05
2,978 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.7848117e-05
3,042 High-Concurrency Locking in R-Trees 1995 VLDB 7.6669657e-05
3,065 Query Processing Method for Multi-Attribute Clustered Relations 1990 VLDB 7.6258862e-05
3,078 Dynamic Density Based Clustering 2017 SIGMOD 7.6041723e-05
3,111 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.5445257e-05
3,141 Transaction Time Indexing with Version Compression 2008 VLDB 7.4910063e-05
3,182 DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search 2020 VLDB 7.4280768e-05
3,206 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3855924e-05
3,259 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3101573e-05
3,278 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2858181e-05
3,294 Spatio-Textual Similarity Joins 2013 VLDB 7.2590482e-05
3,301 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2450912e-05
3,340 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.1987694e-05
3,403 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 7.1338786e-05
3,462 Size Separation Spatial Join 1997 SIGMOD 7.0683581e-05
3,497 Cubetree: Organization of and Bulk Incremental Updates on the Data Cube 1997 SIGMOD 7.0372261e-05
3,528 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 7.0033241e-05
3,530 RE-Tree: An Efficient Index Structure for Regular Expressions 2002 VLDB 7.0008977e-05
Previous Page 3 / 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