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.0011386412
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 282 citing papers.

Rank Citing Paper Year Venue Pagerank
8,402 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 5.3233293e-05
8,592 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.2936565e-05
8,593 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 5.2936565e-05
8,637 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 5.2829747e-05
8,773 LIT: Lightning-fast In-memory Temporal Indexing 2024 SIGMOD 5.2682366e-05
8,801 The Case for Distance-Bounded Spatial Approximations 2021 CIDR 5.2602775e-05
8,813 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 5.2570736e-05
8,829 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2533436e-05
8,834 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2524856e-05
8,844 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2501688e-05
8,847 Spatial Queries with Two kNN Predicates 2012 VLDB 5.2495672e-05
8,881 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 5.2442249e-05
8,883 Adaptive Index Structures 2002 VLDB 5.2436823e-05
8,990 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.2300111e-05
9,080 Distributed Evaluation of Top-k Temporal Joins 2016 SIGMOD 5.2106452e-05
9,176 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 5.200391e-05
9,207 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 5.1943724e-05
9,235 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.1884043e-05
9,289 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 5.1860131e-05
9,307 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.1859125e-05
9,308 Spatial Priority Search: An Access Technique for Scaleless Maps 1991 SIGMOD 5.1855419e-05
9,312 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 5.1841624e-05
9,440 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 5.163285e-05
9,441 On Optimal Node Splitting for R-trees 1998 VLDB 5.163285e-05
9,450 Range-based Obstructed Nearest Neighbor Queries 2016 SIGMOD 5.1613384e-05
9,463 Boosting Moving Object Indexing through Velocity Partitioning 2012 VLDB 5.1592099e-05
9,542 Main-Memory Operation Buffering for Efficient R-Tree Update 2007 VLDB 5.151324e-05
9,560 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.1473114e-05
9,579 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.141601e-05
9,619 Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases 2005 VLDB 5.1376962e-05
9,631 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1362663e-05
9,648 Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories 2014 VLDB 5.132694e-05
9,794 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 5.115551e-05
9,875 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.1049486e-05
10,042 BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data 2024 SIGMOD 5.0786422e-05
10,085 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.0707008e-05
10,100 Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs 2024 SIGMOD 5.068372e-05
10,128 Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search 2025 VLDB 5.0615166e-05
10,206 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.0491152e-05
10,243 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.0414736e-05
10,378 AITTI: Augmented Interval Tree for Temporal Indexing 2027 SIGMOD 4.9605343e-05
10,637 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD 4.9605343e-05
10,707 Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph 2026 SIGMOD 4.9605343e-05
10,822 Toward Drift-Aware Database Benchmarking 2026 VLDB 4.9605343e-05
10,833 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB 4.9605343e-05
10,938 CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data 2026 VLDB 4.9605343e-05
11,118 Elastic Index Selection for Label-Hybrid AKNN Search 2026 VLDB 4.9605343e-05
11,129 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.9605343e-05
11,145 MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance 2026 VLDB 4.9605343e-05
11,703 High-Performance Spatial Data Analytics: Systematic R&D for Scale-Out and Scale-Up Solutions from the Past to Now 2024 VLDB 4.9605343e-05
Previous Page 5 / 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.0019892478
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031562001
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,085 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
2 968 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB
3 7,324 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,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
6 3,678 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD
7 1,412 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,869 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD