Database Paper Browser

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
2496
Venue
SIGMOD
Year
1990
Pagerank
0.0016162015
Overall Rank
6 | 99.97%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 278 citing papers.

Rank Citing Paper Year Venue Pagerank
11,655 Top-k Queries over Digital Traces 2019 SIGMOD 4.1945683e-05
11,769 Efficient Ad-Hoc Graph Inference and Matching in Biological Databases 2017 SIGMOD 4.1945683e-05
11,855 Range Thresholding on Streams 2016 SIGMOD 4.1945683e-05
11,929 Processing of Probabilistic Skyline Queries Using MapReduce 2015 VLDB 4.1945683e-05
11,942 AIDE: An Automatic User Navigation System for Interactive Data Exploration 2015 VLDB 4.1945683e-05
12,060 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.1945683e-05
12,091 QuEval: Beyond high-dimensional indexing a la carte 2013 VLDB 4.1945683e-05
12,106 Indexability of 2D Range Search Revisited: Constant Redundancy and Weak Indivisibility 2012 PODS 4.1945683e-05
12,269 Efficient Skyline Evaluation over Partially Ordered Domains 2010 VLDB 4.1945683e-05
12,277 Transforming Range Queries To Equivalent Box Queries To Optimize Page Access 2010 VLDB 4.1945683e-05
12,411 Towards Efficient Main-Memory Use For Optimum Tree Index Update 2008 VLDB 4.1945683e-05
12,466 IndeGS: Index Supported Graphics Data Server for CFD Data Postprocessing 2007 VLDB 4.1945683e-05
12,497 Efficient Query Processing on Unstructured Tetrahedral Meshes 2006 SIGMOD 4.1945683e-05
12,501 CS Cache Engine: Data Access Accelerator for Location-Based Services in Mobile Environments 2006 SIGMOD 4.1945683e-05
12,521 Indexing for Function Approximation 2006 VLDB 4.1945683e-05
12,564 Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases 2005 VLDB 4.1945683e-05
12,583 ITQS: An Integrated Transport Query System 2004 SIGMOD 4.1945683e-05
12,601 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.1945683e-05
12,625 The ND-Tree: A Dynamic Indexing Technique for Multidimensional Non-ordered Discrete Data Spaces 2003 VLDB 4.1945683e-05
12,628 Improving Performance with Bulk-Inserts in Oracle R-Trees 2003 VLDB 4.1945683e-05
12,651 A One-Pass Aggregation Algorithm with the Optimal Buffer Size in Multidimensional OLAP 2002 VLDB 4.1945683e-05
12,670 Fast Evaluation Techniques for Complex Similarity Queries 2001 VLDB 4.1945683e-05
12,671 An Extendible Hash for Multi-Precision Similarity Querying of Image Databases 2001 VLDB 4.1945683e-05
12,747 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.1945683e-05
12,751 Algorithms for Querying by Spatial Structure 1998 VLDB 4.1945683e-05
12,756 Multimedia Support for Databases 1997 PODS 4.1945683e-05
12,805 Paradise: A Database System for GIS Applications 1995 SIGMOD 4.1945683e-05
14,114 GENESYS: A System for Efficient Spatial Query Processing 1994 SIGMOD -
Previous Page 6 / 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.0032169493
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065631356
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
9,767 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2856106e-05
838 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00016088938
7,054 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8496866e-05
148 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041182766
3,255 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3160522e-05
3,650 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 6.8783391e-05
1,528 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011497734
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032169493
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083378538
2,030 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7378136e-05