Database Paper Browser

Back to papers

The R+-Tree: A Dynamic Index For Multi-Dimensional Objects

Summary: R+-tree: dynamic index for multi-dimensional objects; variant of R-tree that eliminates internal-node overlaps to lower search cost. Algorithms for search/insert/packing/reorganization; up to 50% fewer disk accesses vs. R-tree on large rectangle sets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
7835
Venue
VLDB
Year
1987
Pagerank
0.00083300888
Overall Rank
24 | 99.84%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 121 citing papers.

Rank Citing Paper Year Venue Pagerank
2,592 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 8.4841264e-05
2,673 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.3323551e-05
2,676 Effectively Learning Spatial Indices 2020 VLDB 8.326321e-05
2,905 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 7.9364369e-05
3,042 High-Concurrency Locking in R-Trees 1995 VLDB 7.6669657e-05
3,111 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.5445257e-05
3,278 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2858181e-05
3,340 Fast Time-Series Searching with Scaling and Shifting 1999 PODS 7.1987694e-05
3,462 Size Separation Spatial Join 1997 SIGMOD 7.0683581e-05
3,528 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 7.0033241e-05
3,653 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 6.8725114e-05
3,794 OODB Indexing by Class-Division 1995 SIGMOD 6.7556886e-05
3,902 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.6454492e-05
4,544 On Indexing Line Segments 1990 VLDB 6.0939082e-05
4,613 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.0427196e-05
4,669 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.0039237e-05
4,683 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 5.9940496e-05
4,778 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 5.9259497e-05
4,793 Toward Practical Constraint Databases 1993 VLDB 5.9107617e-05
5,013 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 5.7533424e-05
5,194 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.6318244e-05
5,463 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 5.4920768e-05
5,464 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.4920667e-05
5,469 Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data 1995 PODS 5.4895279e-05
5,661 Trip Planning by an Integrated Search Paradigm 2018 SIGMOD 5.3859487e-05
5,751 Query Processing for Distance Metrics 1990 VLDB 5.3396192e-05
5,889 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.2842168e-05
5,955 Spatial Independent Range Sampling 2021 SIGMOD 5.2539404e-05
5,987 External Memory Algorithms 1998 PODS 5.2399221e-05
6,055 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.2297716e-05
6,098 Two-dimensional Substring Indexing 2001 PODS 5.2078399e-05
6,161 Conflict Resolution Of Rules Assigning Values To Virtual Attributes 1989 SIGMOD 5.1744348e-05
6,268 MATE: Multi-Attribute Table Extraction 2022 VLDB 5.1288179e-05
6,316 On the Effects of Dimensionality Reduction on High Dimensional Similarity Search 2001 PODS 5.1098143e-05
6,473 Efficient Search of Multidimensional B-Trees 1995 VLDB 5.0427056e-05
6,569 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.0017701e-05
6,765 The hBII-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation 1995 VLDB 4.9285619e-05
6,778 A New Method for Similarity Indexing of Market Basket Data 1999 SIGMOD 4.9237313e-05
6,806 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 4.917024e-05
6,988 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 4.8665394e-05
7,046 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8471584e-05
7,048 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 4.8460286e-05
7,601 Query Processing Techniques for Multiversion Access Methods 1996 VLDB 4.6967949e-05
7,635 On Nearest Neighbor Indexing of Nonlinear Trajectories 2003 PODS 4.6864934e-05
7,653 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 4.6831774e-05
7,772 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 4.6509661e-05
8,013 Constraint-Based Query Optimization for Spatial Databases 1991 PODS 4.6021663e-05
8,107 Adaptive Location Constraint Processing 2007 SIGMOD 4.5811252e-05
8,200 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 4.5556029e-05
8,354 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 4.5329424e-05
Previous Page 2 / 3 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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.0032118946
5 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0018380955
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065500256
75 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00057450043
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,046 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8471584e-05
2,139 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB 9.4618572e-05
2,592 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 8.4841264e-05
9,769 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 4.2815042e-05
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
9,209 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR 4.3691119e-05
3,259 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3101573e-05
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032118946
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05