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
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
41 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00046675394
46 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00044853085
56 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00040719947
85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00035405879
93 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00034701237
145 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029548428
202 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00025454884
277 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022537944
291 OPTICS: Ordering Points To Identify the Clustering Structure 1999 SIGMOD 0.00022264197
308 Shooting Stars in the Sky: An Online Algorithm for Skyline Queries 2002 VLDB 0.00021787597
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
351 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00020424271
354 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00020355578
371 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00019869565
402 Fuzzy Queries in Multimedia Database Systems 1998 PODS 0.00019072958
449 Query Processing in Spatial Network Databases 2003 VLDB 0.0001826404
468 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017986163
483 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017756569
522 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00017133516
546 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016734556
560 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00016525569
578 Efficient Algorithms for Mining Outliers from Large Data Sets 2000 SIGMOD 0.00016221871
581 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016153395
592 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00016029789
606 Mining Quantitative Association Rules in Large Relational Tables 1996 SIGMOD 0.00015804851
623 An Optimal and Progressive Algorithm for Skyline Queries 2003 SIGMOD 0.00015684963
675 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00015080025
705 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014829964
726 Client-Server Paradise 1994 VLDB 0.0001460632
728 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014542772
797 Dimensionality Reduction for Similarity Searching in Dynamic Databases 1998 SIGMOD 0.00013927251
810 Similarity-Based Queries for Time Series Data 1997 SIGMOD 0.00013874464
815 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013835761
864 The Pyramid-Technique: Towards Breaking the Curse of Dimensionality 1998 SIGMOD 0.00013522522
896 On Indexing Mobile Objects 1999 PODS 0.0001334014
936 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00013092484
957 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00012962576
994 Spatial Hash-Joins 1996 SIGMOD 0.00012764684
1,025 An Efficient and Scalable Approach to CNN Queries in a Road Network 2005 VLDB 0.00012578515
1,046 Warping Indexes with Envelope Transforms for Query by Humming 2003 SIGMOD 0.00012440091
1,067 Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce 2013 VLDB 0.00012327784
1,100 Range Queries in OLAP Data Cubes 1997 SIGMOD 0.00012169143
1,129 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00012061727
1,137 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00012027131
1,139 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.0001202217
1,174 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00011817414
1,175 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00011812263
1,201 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00011674339
1,212 Efficient Query Processing in Geographic Web Search Engines 2006 SIGMOD 0.00011647465
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.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