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.0011402175
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
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045755116
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00045027197
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040363819
74 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037145866
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034847854
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029048509
207 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024976482
281 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022303081
300 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00021800242
313 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021301023
336 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020652147
363 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019980483
364 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00019978187
385 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019456733
413 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00018686769
459 Query Processing in Spatial Network Databases 2003 VLDB 0.00017860573
479 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017623894
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017451091
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016874202
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016599925
574 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00016165512
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016118297
583 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00015952617
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015759877
620 Mining Quantitative Association Rules in Large Relational Tables 1996 SIGMOD 0.00015495576
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015331662
648 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015156941
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014769852
744 Client-Server Paradise 1994 VLDB 0.00014305129
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014239937
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013744009
829 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.0001360545
839 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.0001354488
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013253709
926 On Indexing Mobile Objects 1999 PODS 0.00013041631
967 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012803465
985 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00012679233
994 Spatial Hash-Joins 1996 SIGMOD 0.00012630797
1,048 An Efficient and Scalable Approach to CNN Queries in a Road Network 2005 VLDB 0.00012297664
1,071 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00012169176
1,081 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012126286
1,107 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00011988445
1,129 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.00011899744
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011843746
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.0001176973
1,178 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011627256
1,188 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00011598149
1,229 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00011421502
1,232 Efficient Query Processing in Geographic Web Search Engines 2006 SIGMOD 0.00011406666
Previous Page 1 / 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.0019923528
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031633451
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,053 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
2 967 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB
3 7,306 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,035 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
6 3,671 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,862 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD