DBScholar

Back to papers

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

Summary: Introduces R+-trees, a dynamic multidimensional index that eliminates overlapping rectangles in internal nodes through object duplication/splitting. Detailed search, update, packing, and reorganization algorithms yield up to 50% fewer disk accesses than R-trees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h9caa095d5ed2fd55
Venue
VLDB
Year
1987
Pagerank
0.00045231517
Overall Rank
44 | 99.71%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{sellis_vldb87,
        title = {{The R+-Tree: A Dynamic Multi-Dimensional Index for Objects}},
        author = {Sellis, Timos and Roussopoulos, Nick and Faloutsos, Christos},
        journal = {PVLDB},
        series = {{VLDB} '87},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 48 of 98 citing papers.

Rank Citing Paper Year Venue Pagerank
4,522 Query Processing for Distance Metrics 1990 VLDB 6.5492954e-05
4,685 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.4533027e-05
4,879 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.3567479e-05
4,980 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.3167773e-05
5,041 MATE: Multi-Attribute Table Extraction 2022 VLDB 6.2899676e-05
5,050 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.2866655e-05
5,313 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 6.1696238e-05
5,350 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1545256e-05
5,835 Spatial Independent Range Sampling 2021 SIGMOD 5.9606673e-05
5,970 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.9116326e-05
5,977 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9106575e-05
6,020 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.8934229e-05
6,165 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.8501981e-05
6,427 External Memory Algorithms 1998 PODS 5.7713075e-05
6,535 Trip Planning by an Integrated Search Paradigm 2018 SIGMOD 5.7356177e-05
6,604 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.7196547e-05
6,631 Two-dimensional Substring Indexing 2001 PODS 5.7114931e-05
6,780 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.6685383e-05
6,810 Conflict Resolution Of Rules Assigning Values To Virtual Attributes 1989 SIGMOD 5.6602648e-05
6,924 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.6292653e-05
7,306 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.5452852e-05
7,324 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.5387994e-05
7,477 The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation 1995 VLDB 5.5022037e-05
7,754 Query Processing Techniques for Multiversion Access Methods 1996 VLDB 5.443551e-05
7,811 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.432001e-05
7,858 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 5.4229689e-05
8,391 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3248747e-05
8,505 Provenance-based Data Skipping 2022 VLDB 5.3126038e-05
8,637 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 5.2829747e-05
8,829 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2533436e-05
8,883 Adaptive Index Structures 2002 VLDB 5.2436823e-05
8,981 Adaptive Location Constraint Processing 2007 SIGMOD 5.2326057e-05
8,990 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.2300111e-05
9,307 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.1859125e-05
9,478 Odyssey: A Journey in the Land of Distributed Data Series Similarity Search 2023 VLDB 5.1576017e-05
9,560 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.1473114e-05
9,619 Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases 2005 VLDB 5.1376962e-05
9,953 SkyPIE: A Fast & Accurate Oracle for Object Placement 2024 SIGMOD 5.0910746e-05
10,085 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.0707008e-05
10,206 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.0491152e-05
10,243 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.0414736e-05
12,446 Supporting Data Uncertainty in Array Databases 2015 SIGMOD 4.9605343e-05
12,572 Data-driven Neuroscience: Enabling Breakthroughs Via Innovative Data Management 2013 SIGMOD 4.9605343e-05
12,598 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.9605343e-05
13,028 Efficient Query Processing on Unstructured Tetrahedral Meshes 2006 SIGMOD 4.9605343e-05
13,052 Indexing for Function Approximation 2006 VLDB 4.9605343e-05
13,131 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.9605343e-05
13,277 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.9605343e-05
Previous Page 2 / 2 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.0019892478
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081207565
102 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033850505
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031562001
1,869 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4516156e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,050 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD
2 1,965 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB
3 2,818 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD
4 10,085 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
5 90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB
6 9,579 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR
7 3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
8 4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD
9 2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD
10 1,869 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD