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
8025
Venue
VLDB
Year
1987
Pagerank
0.00046170812
Overall Rank
42 | 99.72%
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,569 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.6255507e-05
4,751 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.5241784e-05
4,844 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.4826356e-05
4,914 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.4477987e-05
5,183 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 6.3286498e-05
5,202 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.3194496e-05
5,479 MATE: Multi-Attribute Table Extraction 2022 VLDB 6.204351e-05
5,692 Spatial Independent Range Sampling 2021 SIGMOD 6.119196e-05
5,798 Query Processing for Distance Metrics 1990 VLDB 6.0856815e-05
5,838 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 6.0702428e-05
5,857 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 6.0644613e-05
5,888 Clustering Techniques for Minimizing External Path Length 1996 VLDB 6.0498293e-05
6,025 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 6.002739e-05
6,289 External Memory Algorithms 1998 PODS 5.9261616e-05
6,390 Trip Planning by an Integrated Search Paradigm 2018 SIGMOD 5.8895166e-05
6,459 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.8727182e-05
6,491 Two-dimensional Substring Indexing 2001 PODS 5.8641664e-05
6,636 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.8172769e-05
6,660 Conflict Resolution Of Rules Assigning Values To Virtual Attributes 1989 SIGMOD 5.8101577e-05
6,777 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.7773009e-05
7,140 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.6928705e-05
7,151 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.6873519e-05
7,310 The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation 1995 VLDB 5.6494751e-05
7,595 Query Processing Techniques for Multiversion Access Methods 1996 VLDB 5.5888857e-05
7,632 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.5777517e-05
7,681 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 5.5683442e-05
8,200 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.4677285e-05
8,442 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 5.4246876e-05
8,689 Adaptive Index Structures 2002 VLDB 5.3843737e-05
8,787 Adaptive Location Constraint Processing 2007 SIGMOD 5.3729697e-05
8,796 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.3702721e-05
8,889 Provenance-based Data Skipping 2022 VLDB 5.3512428e-05
9,099 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.3250598e-05
9,278 Odyssey: A Journey in the Land of Distributed Data Series Similarity Search 2023 VLDB 5.2936898e-05
9,343 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.2854091e-05
9,544 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2528121e-05
9,735 SkyPIE: A Fast & Accurate Oracle for Object Placement 2024 SIGMOD 5.227679e-05
9,887 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.2006273e-05
9,974 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.1845938e-05
10,015 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.17669e-05
12,104 Supporting Data Uncertainty in Array Databases 2015 SIGMOD 5.093636e-05
12,232 Data-driven Neuroscience: Enabling Breakthroughs Via Innovative Data Management 2013 SIGMOD 5.093636e-05
12,258 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 5.093636e-05
12,690 Efficient Query Processing on Unstructured Tetrahedral Meshes 2006 SIGMOD 5.093636e-05
12,714 Indexing for Function Approximation 2006 VLDB 5.093636e-05
12,757 Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases 2005 VLDB 5.093636e-05
12,794 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 5.093636e-05
12,940 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 5.093636e-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.0020210012
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00082404462
96 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00034590762
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.0003221055
1,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.6928497e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,978 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD
2 1,901 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB
3 2,776 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD
4 9,887 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB
5 85 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB
6 9,365 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR
7 2,974 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,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD