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
2497
Venue
SIGMOD
Year
1990
Pagerank
0.0016113151
Overall Rank
6 | 99.97%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 279 citing papers.

Rank Citing Paper Year Venue Pagerank
3,018 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.6995792e-05
3,042 High-Concurrency Locking in R-Trees 1995 VLDB 7.6669657e-05
3,078 Dynamic Density Based Clustering 2017 SIGMOD 7.6041723e-05
3,080 Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor 2009 VLDB 7.5993605e-05
3,111 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.5445257e-05
3,199 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 7.3999833e-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,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,418 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.1129681e-05
3,522 FTW: Fast Similarity Search under the Time Warping Distance 2005 PODS 7.0086323e-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
3,549 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9792126e-05
3,629 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 6.8997167e-05
3,653 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 6.8725114e-05
3,669 FALCON: Feedback Adaptive Loop for Content-Based Retrieval 2000 VLDB 6.8569375e-05
3,728 Indexing Large Human-Motion Databases 2004 VLDB 6.8082657e-05
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
3,815 Location-based Spatial Queries 2003 SIGMOD 6.7314038e-05
4,035 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 6.5111577e-05
4,173 Spatial Partitioning Techniques in SpatialHadoop 2015 VLDB 6.3776318e-05
4,287 Clue-based Spatio-textual Query 2017 VLDB 6.2824978e-05
4,446 Retrieving Top-k Prestige-Based Relevant Spatial Web Objects 2010 VLDB 6.174662e-05
4,539 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.0982886e-05
4,556 Learning User Preferences By Adaptive Pairwise Comparison 2015 VLDB 6.0815983e-05
4,613 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.0427196e-05
4,622 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 6.0356382e-05
4,683 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 5.9940496e-05
4,738 Joining Interval Data in Relational Databases 2004 SIGMOD 5.9526916e-05
4,778 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 5.9259497e-05
4,792 YADING: Fast Clustering of Large-Scale Time Series Data 2015 VLDB 5.9132429e-05
4,896 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 5.8467149e-05
5,061 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.717245e-05
5,194 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.6318244e-05
5,197 Overlap Interval Partition Join 2014 SIGMOD 5.6308314e-05
5,280 The 3W Model and Algebra for Unified Data Mining 2000 VLDB 5.5851818e-05
5,294 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 5.5777973e-05
5,314 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 5.5702825e-05
5,340 Efficient Computation of Temporal Aggregates with Range Predicates 2001 PODS 5.559394e-05
5,413 POIsam: a System for Efficient Selection of Large-scale Geospatial Data on Maps 2018 SIGMOD 5.5196685e-05
5,463 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 5.4920768e-05
5,464 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.4920667e-05
5,469 Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data 1995 PODS 5.4895279e-05
5,667 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.3823876e-05
5,747 Hercules Against Data Series Similarity Search 2022 VLDB 5.3427166e-05
5,864 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.2947135e-05
5,883 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 5.2865165e-05
5,889 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2842168e-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.0032118946
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065500256
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,769 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2815042e-05
833 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016085787
7,046 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8471584e-05
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
3,259 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3101573e-05
3,653 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 6.8725114e-05
1,519 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011535609
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032118946
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05