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
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045773967
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040370171
74 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00037091678
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029061754
206 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024986675
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
300 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00021810545
313 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021311041
335 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020660268
363 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00019987463
364 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00019976696
385 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.0001946565
412 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00018694414
458 Query Processing in Spatial Network Databases 2003 VLDB 0.00017868943
478 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017631293
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017457851
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016880616
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016607433
574 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00016173068
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016121388
583 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00015960125
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015766567
620 Mining Quantitative Association Rules in Large Relational Tables 1996 SIGMOD 0.00015502611
638 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015338893
650 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00015149775
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014775707
743 Client-Server Paradise 1994 VLDB 0.00014311524
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014246504
811 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013745617
829 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013611445
837 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013551047
886 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.0001325914
926 On Indexing Mobile Objects 1999 PODS 0.00013047723
965 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012809362
985 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00012685169
994 Spatial Hash-Joins 1996 SIGMOD 0.00012636707
1,048 An Efficient and Scalable Approach to CNN Queries in a Road Network 2005 VLDB 0.00012303367
1,070 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00012174775
1,080 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012131978
1,106 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00011994008
1,128 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.00011905274
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011848523
1,157 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00011774968
1,178 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011632691
1,191 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00011590153
1,227 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.000114264
1,230 Efficient Query Processing in Geographic Web Search Engines 2006 SIGMOD 0.00011412036
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.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