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: 2425
Venue: SIGMOD
Year: 1987
Pagerank: 9.6928497e-05
Overall Rank: 1,814 | 87.56%
DOI: 10.1145/38713.38758

Incoming Non-self Citations Over Time

Authors

1. Christos Faloutsos (University of Maryland)
2. Timos Sellis (University of Maryland)
3. Nick Roussopoulos (University of Maryland)

BibTeX Citation

@inproceedings{faloutsos_sigmod87,
        title = {{ANALYSIS OF OBJECT ORIENTED SPATIAL ACCESS METHODS}},
        author = {Faloutsos, Christos and Sellis, Timos and Roussopoulos, Nick},
        series = {{SIGMOD} '87},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/38713.38758},
        url = {https://dl.acm.org/doi/10.1145/38713.38758},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
936	The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems	1990	VLDB	0.00013092484
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,129	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00012061727
1,373	A Model for the Prediction of R-tree Performance	1996	PODS	0.0001098638
1,877	The LSD tree: spatial access to multidimensional point and non-point objects	1989	VLDB	9.5658249e-05
2,168	A Qualitative Comparison Study of Data Structures for Large Line Segment Databases	1992	SIGMOD	9.0469646e-05
2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.7650894e-05
2,774	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	8.1372328e-05
5,183	Twin Grid Files: Space Optimizing Access Schemes	1988	SIGMOD	6.3286498e-05
5,795	Benchmarking Spatial Join Operations with Spatial Output	1995	VLDB	6.0859946e-05
6,025	V-Trees - A Storage Method for Long Vector Data	1994	VLDB	6.002739e-05
6,298	Performance of Data-Parallel Spatial Operations	1994	VLDB	5.9227722e-05
6,777	Techniques for Design and Implementation of Efficient Spatial Access Methods	1988	VLDB	5.7773009e-05
9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB	5.2006273e-05
11,334	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	5.093636e-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.0020210012
8	The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes	1981	SIGMOD	0.00082404462
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.0003221055

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
2	116	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD
3	7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB
4	3,593	The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree	2004	SIGMOD
5	1,373	A Model for the Prediction of R-tree Performance	1996	PODS
6	2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD
7	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
8	2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD
9	42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB
10	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD