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
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051134355
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045609336
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044967652
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.0004024707
75 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037163157
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034749222
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.000289618
210 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024910589
282 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022250557
300 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00021743411
317 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021232519
338 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.0002058961
363 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019931086
364 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00019916561
386 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019396455
413 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00018638335
463 Query Processing in Spatial Network Databases 2003 VLDB 0.00017806376
481 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017567157
490 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017397036
530 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016832286
547 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016545689
576 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00016130425
578 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016079505
587 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00015900873
598 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015711108
622 Mining Quantitative Association Rules in Large Relational Tables 1996 SIGMOD 0.00015452634
640 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015286314
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015142453
687 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014736766
747 Client-Server Paradise 1994 VLDB 0.00014259869
760 Partition Based Spatial-Merge Join 1996 SIGMOD 0.0001419395
812 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013710393
832 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013562724
843 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013501136
889 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013212387
930 On Indexing Mobile Objects 1999 PODS 0.00013000067
968 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012763144
990 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00012637792
999 Spatial Hash-Joins 1996 SIGMOD 0.00012590189
1,053 An Efficient and Scalable Approach to CNN Queries in a Road Network 2005 VLDB 0.00012260546
1,075 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00012129172
1,084 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012086348
1,091 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.0001205609
1,110 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00011949109
1,143 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011810737
1,161 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011733128
1,183 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011589152
1,190 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00011564169
1,235 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00011384515
1,239 Efficient Query Processing in Geographic Web Search Engines 2006 SIGMOD 0.00011374405
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.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