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: 7834
Venue: VLDB
Year: 1987
Pagerank: 0.00083378538
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
2,586	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD	8.4928908e-05
2,672	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3363695e-05
2,678	Effectively Learning Spatial Indices	2020	VLDB	8.3252088e-05
2,900	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB	7.9405413e-05
3,039	High-Concurrency Locking in R-Trees	1995	VLDB	7.6708607e-05
3,107	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD	7.550885e-05
3,275	Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data	2002	SIGMOD	7.2897998e-05
3,338	Fast Time-Series Searching with Scaling and Shifting	1999	PODS	7.2040692e-05
3,457	Size Separation Spatial Join	1997	SIGMOD	7.0755358e-05
3,527	Analysis of n-dimensional Quadtrees Using the Hausdorff Fractal Dimension	1996	VLDB	7.0073154e-05
3,650	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8783391e-05
3,795	OODB Indexing by Class-Division	1995	SIGMOD	6.7604747e-05
3,900	Tight bounds for 2-dimensional indexing schemes	1998	PODS	6.6518011e-05
4,547	On Indexing Line Segments	1990	VLDB	6.0986695e-05
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05
4,672	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0085156e-05
4,692	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	5.9958252e-05
4,780	TOUCH: In-Memory Spatial Join by Hierarchical Data-Oriented Partitioning	2013	SIGMOD	5.9263494e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9164359e-05
5,021	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	5.7548311e-05
5,196	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.6365164e-05
5,458	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	5.496829e-05
5,461	Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data	1995	PODS	5.4947899e-05
5,572	The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data	2023	SIGMOD	5.4277273e-05
5,650	Trip Planning by an Integrated Search Paradigm	2018	SIGMOD	5.3911246e-05
5,756	Query Processing for Distance Metrics	1990	VLDB	5.3401202e-05
5,882	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB	5.2892937e-05
5,953	Spatial Independent Range Sampling	2021	SIGMOD	5.2589924e-05
5,979	External Memory Algorithms	1998	PODS	5.2450009e-05
6,051	Spatial Indexing in Microsoft SQL Server 2008	2008	SIGMOD	5.2347385e-05
6,097	Two-dimensional Substring Indexing	2001	PODS	5.2119402e-05
6,270	MATE: Multi-Attribute Table Extraction	2022	VLDB	5.1337451e-05
6,325	On the Effects of Dimensionality Reduction on High Dimensional Similarity Search	2001	PODS	5.1105081e-05
6,363	Conflict Resolution Of Rules Assigning Values To Virtual Attributes	1989	SIGMOD	5.095005e-05
6,480	Efficient Search of Multidimensional B-Trees	1995	VLDB	5.0475112e-05
6,571	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0061936e-05
6,764	The hBII-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation	1995	VLDB	4.9330419e-05
6,778	A New Method for Similarity Indexing of Market Basket Data	1999	SIGMOD	4.9284526e-05
7,002	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	4.8670742e-05
7,042	LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves	2023	VLDB	4.8541986e-05
7,049	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	4.8505287e-05
7,054	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	4.8496866e-05
7,585	Query Processing Techniques for Multiversion Access Methods	1996	VLDB	4.7037113e-05
7,636	On Nearest Neighbor Indexing of Nonlinear Trajectories	2003	PODS	4.6907372e-05
7,651	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	4.6876337e-05
7,772	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	4.6554316e-05
8,011	Constraint-Based Query Optimization for Spatial Databases	1991	PODS	4.6065603e-05
8,110	Adaptive Location Constraint Processing	2007	SIGMOD	4.5843047e-05
8,201	Efficient Geometry-based Similarity Search of 3D Spatial Databases	1999	SIGMOD	4.5599694e-05
8,359	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	4.5372925e-05

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.0032169493
5	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.0018397217
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065631356
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,672	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.0085156e-05
2,136	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB	9.4721139e-05
2,586	Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data	1991	SIGMOD	8.4928908e-05
9,767	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2856106e-05
129	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.0004429571
9,207	Rethinking Choices for Multi-dimensional Point Indexing: Making the Case for the Often Ignored Quadtree	2007	CIDR	4.3733038e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
2,030	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.7378136e-05