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
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
65 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00061977022
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
91 M-tree: An Efficient Access Method for Similarity Search in Metric Spaces 1997 VLDB 0.00051785122
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
195 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00035317524
231 A Retrieval Technique for Similar Shapes 1991 SIGMOD 0.00032141918
242 Generalized Search Trees for Database Systems (Extended Abstract) 1995 VLDB 0.00031093647
290 Linear Clustering of Objects with Multiple Attributes 1990 SIGMOD 0.00028845557
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
340 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00026854084
356 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026091196
362 Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases 1995 VLDB 0.00025758421
391 Query Processing in Spatial Network Databases 2003 VLDB 0.00024560891
464 PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries 2001 SIGMOD 0.00022476798
471 FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets 1995 SIGMOD 0.00022348285
479 Multi-Step Processing of Spatial Joins 1994 SIGMOD 0.00022182486
537 Fast Time Sequence Indexing for Arbitrary L_p Norms 2000 VLDB 0.00020650291
574 Distance-Based Indexing For High-Dimensional Metric Spaces 1997 SIGMOD 0.0001987713
595 Influence Sets Based on Reverse Nearest Neighbor Queries 2000 SIGMOD 0.00019459302
665 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00018437125
766 Client-Server Paradise 1994 VLDB 0.0001690298
926 Requirements for Science Data Bases and SciDB 2009 CIDR 0.00015237787
986 Managing Intervals Efficiently in Object-Relational Databases 2000 VLDB 0.00014825631
1,004 On Indexing Mobile Objects 1999 PODS 0.00014694512
1,035 Redundancy in Spatial Databases 1989 SIGMOD 0.00014524981
1,111 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.0001389881
1,171 Processing Queries By Linear Constraints 1997 PODS 0.00013507216
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
1,183 On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract) 1999 PODS 0.00013444058
1,184 On Effective Multi-Dimensional Indexing for Strings 2000 SIGMOD 0.00013442644
1,272 Continuous Nearest Neighbor Search 2002 VLDB 0.00012871443
1,326 Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms 1988 SIGMOD 0.00012571381
1,485 On the Analysis of Indexing Schemes 1997 PODS 0.00011698762
1,499 Efficient Searching with Linear Constraints (Extended Abstract) 1998 PODS 0.00011643887
1,519 A Model for the Prediction of R-tree Performance 1996 PODS 0.00011535609
1,755 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB 0.00010661725
1,830 Relaxing Join and Selection Queries 2006 VLDB 0.0001037611
1,966 LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index 2016 SIGMOD 9.9130791e-05
1,987 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.8561164e-05
2,018 Path Caching: A Technique for Optimal External Searching (Extended Abstract) 1994 PODS 9.7852268e-05
2,056 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.6692561e-05
2,088 Capacity Constrained Assignment in Spatial Databases 2008 SIGMOD 9.5707955e-05
2,108 LISA: A Learned Index Structure for Spatial Data 2020 SIGMOD 9.5283642e-05
2,119 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.5036401e-05
2,232 The DEDALE System for Complex Spatial Queries 1998 SIGMOD 9.2308835e-05
2,245 Parallel R-trees 1992 SIGMOD 9.2048202e-05
2,304 A Demonstration of SpatialHadoop: An Efficient MapReduce Framework for Spatial Data 2013 VLDB 9.0659453e-05
2,471 A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces 1990 SIGMOD 8.7158825e-05
2,519 Concurrency and Recovery in Generalized Search Trees 1997 SIGMOD 8.6048934e-05
Previous Page 1 / 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