Database Paper Browser

Back to papers

The R*-tree: An Efficient and Robust Access Method for Points and Rectangles

Summary: R*-tree: joint optimization of area, margin, and overlap in inner nodes for rectangles and multidimensional points. Extensive experiments on a standardized testbed show it outperforms Guttman’s linear/quadratic R-trees and Greene’s variant across point/rectangle queries and map overlay, with efficient data support and only modest implementation cost. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2496
Venue
SIGMOD
Year
1990
Pagerank
0.0016162015
Overall Rank
6 | 99.97%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 278 citing papers.

Rank Citing Paper Year Venue Pagerank
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.7002798e-05
3,039 High-Concurrency Locking in R-Trees 1995 VLDB 7.6708607e-05
3,071 Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor 2009 VLDB 7.6120001e-05
3,107 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.550885e-05
3,183 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 7.4228241e-05
3,255 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3160522e-05
3,264 Dynamic Density Based Clustering 2017 SIGMOD 7.3094408e-05
3,275 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2897998e-05
3,338 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.2040692e-05
3,400 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 7.1405533e-05
3,417 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.1195863e-05
3,518 FTW: Fast Similarity Search under the Time Warping Distance 2005 PODS 7.0153323e-05
3,526 RE-Tree: An Efficient Index Structure for Regular Expressions 2002 VLDB 7.0078308e-05
3,527 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 7.0073154e-05
3,555 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9772546e-05
3,629 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 6.902069e-05
3,650 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 6.8783391e-05
3,664 FALCON: Feedback Adaptive Loop for Content-Based Retrieval 2000 VLDB 6.8636265e-05
3,726 Indexing Large Human-Motion Databases 2004 VLDB 6.8148202e-05
3,800 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7585633e-05
3,814 Location-based Spatial Queries 2003 SIGMOD 6.7341058e-05
4,070 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.4784181e-05
4,217 Spatial Partitioning Techniques in SpatialHadoop 2015 VLDB 6.3514771e-05
4,525 Retrieving Top-k Prestige-Based Relevant Spatial Web Objects 2010 VLDB 6.1116751e-05
4,529 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.1078661e-05
4,564 Learning User Preferences By Adaptive Pairwise Comparison 2015 VLDB 6.0819005e-05
4,612 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.0484423e-05
4,692 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 5.9958252e-05
4,731 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 5.966659e-05
4,737 Joining Interval Data in Relational Databases 2004 SIGMOD 5.9604127e-05
4,780 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 5.9263494e-05
4,823 YADING: Fast Clustering of Large-Scale Time Series Data 2015 VLDB 5.8956566e-05
4,882 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 5.8548674e-05
5,065 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.7247716e-05
5,190 Overlap Interval Partition Join 2014 SIGMOD 5.6381091e-05
5,196 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.6365164e-05
5,276 The 3W Model and Algebra for Unified Data Mining 2000 VLDB 5.5905507e-05
5,310 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 5.5753015e-05
5,328 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 5.5665496e-05
5,335 Efficient Computation of Temporal Aggregates with Range Predicates 2001 PODS 5.5647464e-05
5,458 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.496829e-05
5,461 Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data 1995 PODS 5.4947899e-05
5,572 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 5.4277273e-05
5,664 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.3821564e-05
5,738 Hercules Against Data Series Similarity Search 2022 VLDB 5.3478528e-05
5,846 POIsam: a System for Efficient Selection of Large-scale Geospatial Data on Maps 2018 SIGMOD 5.3023698e-05
5,860 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.2990241e-05
5,878 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.2916009e-05
5,882 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2892937e-05
5,979 External Memory Algorithms 1998 PODS 5.2450009e-05
Previous Page 3 / 6 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
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065631356
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,767 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2856106e-05
838 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016088938
7,054 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8496866e-05
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
3,255 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3160522e-05
3,650 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 6.8783391e-05
1,528 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011497734
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
2,030 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7378136e-05