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 50 of 98 citing papers.

Rank Citing Paper Year Venue Pagerank
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045773967
45 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.0004503446
90 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00034860244
206 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00024986675
279 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00022308048
335 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020660268
363 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00019987463
418 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00018617842
458 Query Processing in Spatial Network Databases 2003 VLDB 0.00017868943
478 Fast Time Sequence Indexing for Arbitrary Lp Norms 2000 VLDB 0.00017631293
488 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00017457851
527 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00016880616
545 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00016607433
597 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.00015766567
743 Client-Server Paradise 1994 VLDB 0.00014311524
837 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00013551047
887 Requirements for Science Data Bases and SciDB 2009 CIDR 0.00013258595
926 On Indexing Mobile Objects 1999 PODS 0.00013047723
994 Spatial Hash-Joins 1996 SIGMOD 0.00012636707
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00012393393
1,128 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.00011905274
1,237 Processing Queries By Linear Constraints 1997 PODS 0.00011396286
1,304 Continuous Nearest Neighbor Search 2002 VLDB 0.00011104243
1,446 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 0.00010629222
1,464 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00010580339
1,530 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 0.00010344205
1,559 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00010252232
1,589 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00010139591
1,643 Relaxing Join and Selection Queries 2006 VLDB 0.00010006399
1,813 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 9.5801503e-05
1,878 Effectively Learning Spatial Indices 2020 VLDB 9.4451309e-05
1,922 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3751198e-05
2,016 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1771614e-05
2,162 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.935022e-05
2,179 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 8.9120272e-05
2,358 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5817166e-05
2,367 Capacity Constrained Assignment in Spatial Databases 2008 SIGMOD 8.5623448e-05
2,388 Parallel R-trees 1992 SIGMOD 8.5375939e-05
2,588 Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations 1997 VLDB 8.2518251e-05
2,706 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 8.1111109e-05
2,828 Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data 1991 SIGMOD 7.9650643e-05
2,858 A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data 2013 VLDB 7.9354625e-05
3,099 The DEDALE System for Complex Spatial Queries 1998 SIGMOD 7.6508573e-05
3,120 Size Separation Spatial Join 1997 SIGMOD 7.6300049e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,347 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3933163e-05
3,669 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD 7.1125618e-05
3,859 OODB Indexing by Class-Division 1995 SIGMOD 6.9667626e-05
4,060 Tight bounds for 2-dimensional indexing schemes 1998 PODS 6.8250997e-05
4,155 Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension 1996 VLDB 6.7762032e-05
Previous Page 1 / 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