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
8,474 Adaptive Index Structures 2002 VLDB 4.5029015e-05
8,497 DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph 2025 SIGMOD 4.4981377e-05
8,580 LIT: Lightning-fast In-memory Temporal Indexing 2024 SIGMOD 4.492241e-05
8,592 Boosting Moving Object Indexing through Velocity Partitioning 2012 VLDB 4.4894309e-05
8,601 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 4.4875358e-05
8,629 Spatial Queries with Two kNN Predicates 2012 VLDB 4.4809879e-05
8,636 WISK: A Workload-aware Learned Index for Spatial Keyword Queries 2023 SIGMOD 4.4801284e-05
8,638 The Case for Distance-Bounded Spatial Approximations 2021 CIDR 4.4797417e-05
8,647 A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases 2006 SIGMOD 4.4768766e-05
8,693 A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems 2021 SIGMOD 4.466142e-05
8,709 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 4.4638829e-05
8,810 Spatial Priority Search: An Access Technique for Scaleless Maps 1991 SIGMOD 4.4442316e-05
8,825 Determining the Impact Regions of Competing Options in Preference Space 2017 SIGMOD 4.4415078e-05
8,857 Distributed Evaluation of Top-k Temporal Joins 2016 SIGMOD 4.4345027e-05
8,894 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 4.4274507e-05
8,895 Fast and Adaptive Indexing of Multi-Dimensional Observational Data 2016 VLDB 4.427268e-05
8,925 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 4.427232e-05
8,948 One Seed, Two Birds: A Unified Learned Structure for Exact and Approximate Counting 2024 SIGMOD 4.423786e-05
8,952 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 4.423107e-05
9,017 Indexing Medium-dimensionality Data in Oracle 1999 SIGMOD 4.4091374e-05
9,018 On Optimal Node Splitting for R-trees 1998 VLDB 4.4091374e-05
9,116 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 4.3928853e-05
9,143 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3850454e-05
9,207 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 4.3733038e-05
9,258 Main-Memory Operation Buffering for Efficient R-Tree Update 2007 VLDB 4.3690661e-05
9,307 Range-based Obstructed Nearest Neighbor Queries 2016 SIGMOD 4.3571035e-05
9,358 Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories 2014 VLDB 4.3510473e-05
9,427 A Generic Framework for Handling Uncertain Data with Local Correlations 2011 VLDB 4.3441378e-05
9,531 An Experimental Evaluation and Investigation of Waves of Misery in R-trees 2022 VLDB 4.3274164e-05
9,767 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2856106e-05
9,827 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 4.2751057e-05
9,853 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 4.2711871e-05
10,039 VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs 2026 SIGMOD 4.1945683e-05
10,073 Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph 2026 SIGMOD 4.1945683e-05
10,158 Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph 2026 SIGMOD 4.1945683e-05
10,303 Elastic Index Selection for Label-Hybrid AKNN Search 2026 VLDB 4.1945683e-05
10,314 Index Intersection for High-Dimensional Range Queries 2026 VLDB 4.1945683e-05
10,331 MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance 2026 VLDB 4.1945683e-05
10,384 OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves 2025 SIGMOD 4.1945683e-05
10,507 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 4.1945683e-05
10,602 Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates 2025 VLDB 4.1945683e-05
10,737 Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search 2025 VLDB 4.1945683e-05
10,980 BT-Tree: A Reinforcement Learning Based Index for Big Trajectory Data 2024 SIGMOD 4.1945683e-05
10,988 Finding Logic Bugs in Spatial Database Engines via Affine Equivalent Inputs 2024 SIGMOD 4.1945683e-05
11,126 High-Performance Spatial Data Analytics: Systematic R&D for Scale-Out and Scale-Up Solutions from the Past to Now 2024 VLDB 4.1945683e-05
11,128 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.1945683e-05
11,335 Faster and Better Solution to Embed Lp Metrics by Tree Metrics 2022 SIGMOD 4.1945683e-05
11,361 Approximate Range Thresholding 2022 SIGMOD 4.1945683e-05
11,367 tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space 2022 SIGMOD 4.1945683e-05
11,593 Recommending Deployment Strategies for Collaborative Tasks 2020 SIGMOD 4.1945683e-05
Previous Page 5 / 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