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.00045337853
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,501 Query Processing for Distance Metrics 1990 VLDB 6.5741203e-05
4,670 Supporting Frequent Updates in R-Trees: A Bottom-Up Approach 2003 VLDB 6.47772e-05
4,850 The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data 2023 SIGMOD 6.3808017e-05
4,956 TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning 2013 SIGMOD 6.340462e-05
5,023 A General Solution of the n-dimensional B-tree Problem 1995 SIGMOD 6.3096704e-05
5,276 MATE: Multi-Attribute Table Extraction 2022 VLDB 6.2002884e-05
5,292 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 6.1924532e-05
5,328 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1778312e-05
5,819 Spatial Independent Range Sampling 2021 SIGMOD 5.9832748e-05
5,957 Improving Adaptable Similarity Query Processing by Using Approximations 1998 VLDB 5.93405e-05
5,963 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9330399e-05
6,007 Clustering Techniques for Minimizing External Path Length 1996 VLDB 5.9155532e-05
6,145 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.8717297e-05
6,413 External Memory Algorithms 1998 PODS 5.7931958e-05
6,521 Trip Planning by an Integrated Search Paradigm 2018 SIGMOD 5.7573717e-05
6,595 LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves 2023 VLDB 5.7413481e-05
6,616 Two-dimensional Substring Indexing 2001 PODS 5.7330951e-05
6,756 Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size 2021 SIGMOD 5.6900378e-05
6,788 Conflict Resolution Of Rules Assigning Values To Virtual Attributes 1989 SIGMOD 5.6816623e-05
6,905 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.6505668e-05
7,289 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 5.5652691e-05
7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 5.5598057e-05
7,454 The hB-Pi-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation 1995 VLDB 5.5230036e-05
7,734 Query Processing Techniques for Multiversion Access Methods 1996 VLDB 5.4640143e-05
7,788 K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization 2007 VLDB 5.4526034e-05
7,837 Efficient Concurrency Control in Multidimensional Access Methods 1999 SIGMOD 5.4434696e-05
8,369 Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing 2023 VLDB 5.3450708e-05
8,495 Provenance-based Data Skipping 2022 VLDB 5.3304338e-05
8,611 Efficient Geometry-based Similarity Search of 3D Spatial Databases 1999 SIGMOD 5.3029766e-05
8,804 SwiftSpatial: Spatial Joins on Modern Hardware 2025 SIGMOD 5.2732683e-05
8,856 Adaptive Index Structures 2002 VLDB 5.2635701e-05
8,950 Adaptive Location Constraint Processing 2007 SIGMOD 5.2524216e-05
8,960 The Impact of Global Clustering on Spatial Database Systems 1994 VLDB 5.249844e-05
9,273 Are Window Queries Representative For Arbitrary Range Queries? 1996 PODS 5.2055814e-05
9,440 Odyssey: A Journey in the Land of Distributed Data Series Similarity Search 2023 VLDB 5.1771634e-05
9,522 R-Tree Based Indexing of Now-Relative Bitemporal Data 1998 VLDB 5.1668323e-05
9,911 SkyPIE: A Fast & Accurate Oracle for Object Placement 2024 SIGMOD 5.1103839e-05
10,048 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.0899328e-05
10,168 PLATON: Top-down R-tree Packing with Learned Partition Policy 2023 SIGMOD 5.0682654e-05
10,204 Dynamic Update Cube for Range-Sum Queries 2001 VLDB 5.0605896e-05
12,397 Supporting Data Uncertainty in Array Databases 2015 SIGMOD 4.9793485e-05
12,523 Data-driven Neuroscience: Enabling Breakthroughs Via Innovative Data Management 2013 SIGMOD 4.9793485e-05
12,549 Statistics Collection in Oracle Spatial and Graph: Fast Histogram Construction for Complex Geometry Objects 2013 VLDB 4.9793485e-05
12,980 Efficient Query Processing on Unstructured Tetrahedral Meshes 2006 SIGMOD 4.9793485e-05
13,004 Indexing for Function Approximation 2006 VLDB 4.9793485e-05
13,047 Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases 2005 VLDB 4.9793485e-05
13,084 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.9793485e-05
13,230 Fast High-Dimensional Data Search in Incomplete Databases 1998 VLDB 4.9793485e-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.001992968
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.0008122792
101 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033937215
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031645463
1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4871409e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,303 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB
2 1,956 A Generic Approach to Bulk Loading Multidimensional Index Structures 1997 VLDB
3 2,828 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD
4 10,048 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,544 Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree 2007 CIDR
7 3,034 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,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD