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
2558
Venue
SIGMOD
Year
1990
Pagerank
0.001157935
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 279 citing papers.

Rank Citing Paper Year Venue Pagerank
6,025 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 6.002739e-05
6,079 FACET: Robust Counterfactual Explanation Analytics 2023 SIGMOD 5.9850223e-05
6,089 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.9806097e-05
6,093 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.978635e-05
6,133 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 5.9654376e-05
6,149 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.9581422e-05
6,176 POIsam: a System for Efficient Selection of Large-scale Geospatial Data on Maps 2018 SIGMOD 5.9496498e-05
6,217 Clue-based Spatio-textual Query 2017 VLDB 5.9425753e-05
6,249 Maximum Rank Query 2015 VLDB 5.9418925e-05
6,289 External Memory Algorithms 1998 PODS 5.9261616e-05
6,298 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.9227722e-05
6,426 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.8809448e-05
6,451 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.8751993e-05
6,459 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.8727182e-05
6,473 Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce 2013 VLDB 5.8698599e-05
6,491 Two-dimensional Substring Indexing 2001 PODS 5.8641664e-05
6,537 Range Search over Encrypted Multi-Attribute Data 2023 VLDB 5.8478276e-05
6,561 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 5.8389373e-05
6,615 A Topology-Aware Localized Update Strategy for Graph-Based ANN Index 2026 VLDB 5.8214312e-05
6,636 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.8172769e-05
6,647 AGILE: Adaptive Indexing for Context-Aware Information Filters 2005 SIGMOD 5.8147547e-05
6,749 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 5.7844585e-05
6,780 Discovering Longest-lasting Correlation in Sequence Databases 2013 VLDB 5.7766335e-05
6,830 Global Immutable Region Computation 2014 SIGMOD 5.759977e-05
6,880 Real-time Distributed Co-Movement Pattern Detection on Streaming Trajectories 2019 VLDB 5.7470112e-05
6,887 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 5.7457967e-05
6,894 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 5.744549e-05
6,953 Trajectory Similarity Measurement: An Efficiency Perspective 2024 VLDB 5.7303405e-05
7,070 Indexing Methods for Moving Object Databases: Games and Other Applications 2013 SIGMOD 5.7116663e-05
7,124 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 5.6961208e-05
7,140 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.6928705e-05
7,151 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.6873519e-05
7,337 OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves 2025 SIGMOD 5.6393827e-05
7,350 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 5.6358517e-05
7,379 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 5.629255e-05
7,402 Scaling and Time Warping in Time Series Querying 2005 VLDB 5.6250511e-05
7,545 An Open Abstract-Object Storage System 1996 SIGMOD 5.602766e-05
7,576 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 5.593012e-05
7,632 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.5777517e-05
7,708 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 5.5628618e-05
7,711 Optimizing Probabilistic Query Processing on Continuous Uncertain Data 2011 VLDB 5.5614818e-05
7,744 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.5541724e-05
7,761 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 5.550467e-05
7,939 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB 5.5181056e-05
8,003 Towards Designing and Learning Piecewise Space-Filling Curves 2023 VLDB 5.5084586e-05
8,048 WISK: A Workload-aware Learned Index for Spatial Keyword Queries 2023 SIGMOD 5.5003171e-05
8,061 Raster Intervals: An Approximation Technique for Polygon Intersection Joins 2023 SIGMOD 5.4953977e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,210 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 5.4661361e-05
8,391 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 5.4356884e-05
Previous Page 4 / 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.0020210012
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.0003221055
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,887 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
2 936 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB
3 7,151 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB
4 145 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD
5 2,974 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
6 3,593 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD
7 1,373 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 42 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB
10 1,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD