Analysis Of Object Oriented Spatial Access Methods

Summary: First known analytic treatment of R-trees; derives 1D formulas and uses higher-dimensional transformation to compare R- and R+-trees. R+-trees require under half the disk accesses of R-trees on real data, especially with many small segments versus few long ones. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2364
Venue: SIGMOD
Year: 1987
Pagerank: 9.7315522e-05
Overall Rank: 2,033 | 85.88%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
833	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00016085787
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,111	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.0001389881
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
1,519	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011535609
2,001	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.8275076e-05
2,144	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.4375327e-05
2,673	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3323551e-05
2,978	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.7848117e-05
5,013	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	5.7533424e-05
5,464	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	5.4920667e-05
5,667	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.3823876e-05
5,864	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	5.2947135e-05
6,569	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.0017701e-05
9,769	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	4.2815042e-05
11,131	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,021	On Optimal Node Splitting for R-trees	1998	VLDB	4.4049428e-05
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065500256
7,046	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	4.8471584e-05
3,653	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD	6.8725114e-05
1,519	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011535609
3,259	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3101573e-05
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032118946
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016113151