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 50 of 278 citing papers.

Rank Citing Paper Year Venue Pagerank
5,997 FACET: Robust Counterfactual Explanation Analytics 2023 SIGMOD 5.2415551e-05
6,012 Clue-based Spatio-textual Query 2017 VLDB 5.2415551e-05
6,051 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.2347385e-05
6,076 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.223696e-05
6,097 Two-dimensional Substring Indexing 2001 PODS 5.2119402e-05
6,202 A Benchmark for Evaluating Moving Object Indexes 2008 VLDB 5.1593242e-05
6,203 Maximum Rank Query 2015 VLDB 5.1590738e-05
6,360 High-Dimensional Vector Similarity Search: From Time Series to Deep Network Embeddings 2020 SIGMOD 5.0961051e-05
6,376 DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search 2024 VLDB 5.0916875e-05
6,424 Range Search over Encrypted Multi-Attribute Data 2023 VLDB 5.0670573e-05
6,441 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.0603113e-05
6,480 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0475112e-05
6,500 Adaptive Multi-Stage Distance Join Processing 2000 SIGMOD 5.0381573e-05
6,512 Trajectory Similarity Measurement: An Efficiency Perspective 2024 VLDB 5.0321577e-05
6,581 Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce 2013 VLDB 5.0030276e-05
6,632 Global Immutable Region Computation 2014 SIGMOD 4.984576e-05
6,671 Discovering Longest-lasting Correlation in Sequence Databases 2013 VLDB 4.9669225e-05
6,705 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 4.9549359e-05
6,742 AGILE: Adaptive Indexing for Context-Aware Information Filters 2005 SIGMOD 4.9432585e-05
6,770 An Incremental Hausdorff Distance Calculation Algorithm 2011 VLDB 4.9317829e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9284526e-05
6,869 An Open Abstract-Object Storage System 1996 SIGMOD 4.9005143e-05
6,946 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB 4.8909775e-05
7,002 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 4.8670742e-05
7,005 Indexing the Edges – A simple and yet efficient approach to high-dimensional indexing 2000 PODS 4.8654221e-05
7,037 Real-time Distributed Co-Movement Pattern Detection on Streaming Trajectories 2019 VLDB 4.8548122e-05
7,042 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 4.8541986e-05
7,049 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 4.8505287e-05
7,054 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8496866e-05
7,203 Indexing Methods for Moving Object Databases: Games and Other Applications 2013 SIGMOD 4.8019323e-05
7,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.792836e-05
7,265 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 4.7834983e-05
7,271 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 4.7813404e-05
7,519 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB 4.7180617e-05
7,540 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 4.7159549e-05
7,544 A Topology-Aware Localized Update Strategy for Graph-Based ANN Index 2026 VLDB 4.7149033e-05
7,578 Scaling and Time Warping in Time Series Querying 2005 VLDB 4.7061534e-05
7,623 Optimizing Probabilistic Query Processing on Continuous Uncertain Data 2011 VLDB 4.6933659e-05
7,636 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 4.6907372e-05
7,729 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6660821e-05
7,772 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 4.6554316e-05
7,791 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 4.6502309e-05
7,837 GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces 2025 VLDB 4.6379694e-05
8,123 Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation 2001 VLDB 4.5801104e-05
8,124 S3: Similarity Search in CAD Database Systems 1997 SIGMOD 4.5801104e-05
8,201 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 4.5599694e-05
8,263 Raster Intervals: An Approximation Technique for Polygon Intersection Joins 2023 SIGMOD 4.5464722e-05
8,359 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 4.5372925e-05
8,405 Towards Designing and Learning Piecewise Space-Filling Curves 2023 VLDB 4.5224126e-05
8,472 Rapidash: Efficient Detection of Constraint Violations 2024 VLDB 4.5036378e-05
Previous Page 4 / 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