DBScholar

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
hf9e5c18551cae259
Venue
SIGMOD
Year
1990
Pagerank
0.0011405675
Overall Rank
4 | 99.98%
DOI
10.1145/93597.98741

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{beckmann_sigmod90,
        title = {{The R*-tree: An Efficient and Robust Access Method for Points and Rectangles}},
        author = {Beckmann, Norbert and Kriegel, Hans-Peter and Schneider, Ralf and Seeger, Bernhard},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.98741},
        url = {https://dl.acm.org/doi/10.1145/93597.98741},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 281 citing papers.

Rank Citing Paper Year Venue Pagerank
2,939 Approximate NN Queries on Streams with Guaranteed Error/performance Bounds 2004 VLDB 7.8340314e-05
3,029 Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor 2009 VLDB 7.737708e-05
3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.7330662e-05
3,045 Spatial Keyword Query Processing: An Experimental Evaluation 2013 VLDB 7.72015e-05
3,057 Dynamic Density Based Clustering 2017 SIGMOD 7.6965352e-05
3,099 The DEDALE System for Complex Spatial Queries 1998 SIGMOD 7.6508573e-05
3,111 High-Concurrency Locking in R-Trees 1995 VLDB 7.6374094e-05
3,182 General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows 2002 SIGMOD 7.561954e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,302 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.4433382e-05
3,332 WALRUS: A Similarity Retrieval Algorithm for Image Databases 1999 SIGMOD 7.4163853e-05
3,333 FTW: Fast Similarity Search under the Time Warping Distance 2005 PODS 7.4153527e-05
3,347 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3933163e-05
3,462 Prediction and Indexing of Moving Objects with Unknown Motion Patterns 2004 SIGMOD 7.2834147e-05
3,638 Location-based Spatial Queries 2003 SIGMOD 7.1446219e-05
3,658 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 7.1243855e-05
3,669 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 7.1125618e-05
3,774 Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces 2006 SIGMOD 7.0277477e-05
3,829 RE-Tree: An Efficient Index Structure for Regular Expressions 2002 VLDB 6.9972992e-05
3,887 Fast Parallel Similarity Search in Multimedia Databases 1997 SIGMOD 6.9458013e-05
3,910 FALCON: Feedback Adaptive Loop for Content-Based Retrieval 2000 VLDB 6.9310405e-05
4,082 Learning User Preferences By Adaptive Pairwise Comparison 2015 VLDB 6.8176001e-05
4,155 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 6.7762032e-05
4,184 YADING: Fast Clustering of Large-Scale Time Series Data 2015 VLDB 6.7540884e-05
4,219 Spatial Partitioning Techniques in SpatialHadoop 2015 VLDB 6.7262869e-05
4,255 Retrieving Top-k Prestige-Based Relevant Spatial Web Objects 2010 VLDB 6.7010852e-05
4,336 Joining Interval Data in Relational Databases 2004 SIGMOD 6.6560067e-05
4,364 An Evaluation of Generic Bulk Loading Techniques 2001 VLDB 6.6343719e-05
4,568 Overlap Interval Partition Join 2014 SIGMOD 6.5300934e-05
4,670 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.47772e-05
4,850 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.3808017e-05
4,927 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3503189e-05
4,956 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.340462e-05
4,983 Indexing Large Human-Motion Databases 2004 VLDB 6.3269506e-05
5,062 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 6.2910498e-05
5,270 Online Event-driven Subsequence Matching over Financial Data Streams 2004 SIGMOD 6.2013771e-05
5,313 Hercules Against Data Series Similarity Search 2022 VLDB 6.1846986e-05
5,328 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1778312e-05
5,527 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 6.0936219e-05
5,594 Efficient Computation of Temporal Aggregates with Range Predicates 2001 PODS 6.0728705e-05
5,619 A Topology-Aware Localized Update Strategy for Graph-Based ANN Index 2026 VLDB 6.062554e-05
5,722 Ranked Subsequence Matching in Time-Series Databases 2007 VLDB 6.0183253e-05
5,779 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 5.9976039e-05
5,863 A Benchmark for Evaluating Moving Object Indexes 2008 VLDB 5.9667924e-05
5,905 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.9509027e-05
5,957 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.93405e-05
5,963 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9330399e-05
6,007 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.9155532e-05
6,020 The 3W Model and Algebra for Unified Data Mining 2000 VLDB 5.9129763e-05
6,032 Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search 2002 SIGMOD 5.9097667e-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.001992968
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031645463
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,048 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
2 965 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB
3 7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB
4 146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD
5 3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
6 3,669 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD
7 1,405 A Model for the Prediction of R-tree Performance 1996 PODS
8 2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD
9 44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB
10 1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD