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
8,377 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 5.3435192e-05
8,566 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.3137327e-05
8,567 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 5.3137327e-05
8,611 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 5.3029766e-05
8,743 LIT: Lightning-fast In-memory Temporal Indexing 2024 SIGMOD 5.2882178e-05
8,774 The Case for Distance-Bounded Spatial Approximations 2021 CIDR 5.2802274e-05
8,786 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 5.2768554e-05
8,804 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2732683e-05
8,809 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2724071e-05
8,818 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 5.2700772e-05
8,820 Spatial Queries with Two kNN Predicates 2012 VLDB 5.2694776e-05
8,852 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 5.2641151e-05
8,856 Adaptive Index Structures 2002 VLDB 5.2635701e-05
8,960 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.249844e-05
9,053 Distributed Evaluation of Top-k Temporal Joins 2016 SIGMOD 5.230408e-05
9,145 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 5.220115e-05
9,172 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 5.2140475e-05
9,204 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 5.2080128e-05
9,255 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 5.2056825e-05
9,273 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.2055814e-05
9,274 Spatial Priority Search: An Access Technique for Scaleless Maps 1991 SIGMOD 5.2051842e-05
9,280 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 5.2036709e-05
9,405 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 5.1828502e-05
9,406 On Optimal Node Splitting for R-trees 1998 VLDB 5.1828502e-05
9,427 Boosting Moving Object Indexing through Velocity Partitioning 2012 VLDB 5.178769e-05
9,503 Main-Memory Operation Buffering for Efficient R-Tree Update 2007 VLDB 5.1708619e-05
9,522 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.1668323e-05
9,524 Range-based Obstructed Nearest Neighbor Queries 2016 SIGMOD 5.1662415e-05
9,544 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 5.1611019e-05
9,597 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1557462e-05
9,612 Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories 2014 VLDB 5.1521611e-05
9,757 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 5.1349531e-05
9,833 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 5.1243105e-05
10,002 BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data 2024 SIGMOD 5.0979044e-05
10,048 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.0899328e-05
10,061 Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs 2024 SIGMOD 5.0875952e-05
10,090 Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search 2025 VLDB 5.0807138e-05
10,168 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.0682654e-05
10,204 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.0605896e-05
10,563 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD 4.9793485e-05
10,635 Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph 2026 SIGMOD 4.9793485e-05
10,751 Toward Drift-Aware Database Benchmarking 2026 VLDB 4.9793485e-05
10,762 RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem 2026 VLDB 4.9793485e-05
10,868 CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data 2026 VLDB 4.9793485e-05
11,048 Elastic Index Selection for Label-Hybrid AKNN Search 2026 VLDB 4.9793485e-05
11,059 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.9793485e-05
11,075 MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance 2026 VLDB 4.9793485e-05
11,650 High-Performance Spatial Data Analytics: Systematic R&D for Scale-Out and Scale-Up Solutions from the Past to Now 2024 VLDB 4.9793485e-05
11,652 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.9793485e-05
11,843 Faster and Better Solution to Embed Lp Metrics by Tree Metrics 2022 SIGMOD 4.9793485e-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.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