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
1,241 Processing Queries By Linear Constraints 1997 PODS 0.00011373551
1,311 Continuous Nearest Neighbor Search 2002 VLDB 0.00011063629
1,411 Towards an Analysis of Range Query Performance in Spatial Data Structures 1993 PODS 0.00010729946
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
1,445 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010607118
1,460 PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search 2020 VLDB 0.00010558941
1,520 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010358287
1,524 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.0001033427
1,532 Column Imprints: A Secondary Index Structure 2013 SIGMOD 0.00010312002
1,549 Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation 1997 SIGMOD 0.00010257684
1,554 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00010236406
1,555 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.0001023212
1,574 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010164216
1,594 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010103178
1,618 Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces 2023 VLDB 0.00010045437
1,649 Relaxing Join and Selection Queries 2006 VLDB 9.9699016e-05
1,725 Spreadsheets in RDBMS for OLAP 2003 SIGMOD 9.7733128e-05
1,729 Closest Pair Queries in Spatial Databases 2000 SIGMOD 9.761101e-05
1,741 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 9.7287344e-05
1,786 ArrayStore: A Storage Manager for Complex Parallel Array Processing 2011 SIGMOD 9.6344047e-05
1,805 The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation 2000 VLDB 9.5936926e-05
1,825 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5443954e-05
1,867 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4581343e-05
1,884 Effectively Learning Spatial Indices 2020 VLDB 9.422145e-05
1,905 Efficient Computation of Reverse Skyline Queries 2007 VLDB 9.3819594e-05
1,921 MindReader: Querying databases through multiple examples 1998 VLDB 9.3580039e-05
1,930 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3453623e-05
1,948 Incremental Clustering for Mining in a Data Warehousing Environment 1998 VLDB 9.30382e-05
1,965 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.2829035e-05
2,029 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1470713e-05
2,076 Query and Update Efficient B+-Tree Based Indexing of Moving Objects 2004 VLDB 9.0622765e-05
2,080 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.058838e-05
2,176 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9031141e-05
2,217 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 8.8230488e-05
2,268 ELPIS: Graph-Based Similarity Search for Scalable Data Science 2023 VLDB 8.7144632e-05
2,322 STRIPES: An Efficient Index for Predicted Trajectories 2004 SIGMOD 8.6301008e-05
2,368 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5495935e-05
2,380 Capacity Constrained Assignment in Spatial Databases 2008 SIGMOD 8.5300815e-05
2,400 Parallel R-trees 1992 SIGMOD 8.5059093e-05
2,415 On Efficient Spatial Matching 2007 VLDB 8.4848606e-05
2,597 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.2212352e-05
2,693 Identifying Similarities, Periodicities and Bursts for Online Search Queries 2004 SIGMOD 8.1107645e-05
2,717 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 8.0808382e-05
2,733 Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search 2020 VLDB 8.0653682e-05
2,735 Efficient Numerical Error Bounding for Replicated Network Services 2000 VLDB 8.0624548e-05
2,818 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 7.9536217e-05
2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9401525e-05
2,879 The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art 2019 VLDB 7.8951769e-05
2,885 Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art 2025 SIGMOD 7.8929868e-05
2,923 Indexing Large Trajectory Data Sets With SETI* 2003 CIDR 7.8423791e-05
Previous Page 2 / 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