DBScholar

Back to papers

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
h41b6f0029bc41ab4
Venue
SIGMOD
Year
1987
Pagerank
9.4516156e-05
Overall Rank
1,869 | 87.48%
DOI
10.1145/38713.38758

Incoming Non-self Citations Over Time

Authors

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
44 The R+-Tree: A Dynamic Multi-Dimensional Index for Objects 1987 VLDB 0.00045231517
760 Partition Based Spatial-Merge Join 1996 SIGMOD 0.0001419395
968 The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems 1990 VLDB 0.00012763144
999 Spatial Hash-Joins 1996 SIGMOD 0.00012590189
1,143 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011810737
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
1,915 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.368237e-05
2,217 A Qualitative Comparison Study of Data Structures for Large Line Segment Databases 1992 SIGMOD 8.8230488e-05
2,368 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5495935e-05
2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9401525e-05
5,313 Twin Grid Files: Space Optimizing Access Schemes 1988 SIGMOD 6.1696238e-05
5,921 Benchmarking Spatial Join Operations with Spatial Output 1995 VLDB 5.9284908e-05
6,165 V-Trees - A Storage Method for Long Vector Data 1994 VLDB 5.8501981e-05
6,431 Performance of Data-Parallel Spatial Operations 1994 VLDB 5.7688769e-05
6,924 Techniques for Design and Implementation of Efficient Spatial Access Methods 1988 VLDB 5.6292653e-05
10,085 Adaptive Indexing of Objects with Spatial Extent 2023 VLDB 5.0707008e-05
11,705 LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization 2024 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

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.0019892478
8 The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes 1981 SIGMOD 0.00081207565
102 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033850505
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031562001
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,441 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,324 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB
4 3,678 The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree 2004 SIGMOD
5 1,412 A Model for the Prediction of R-tree Performance 1996 PODS
6 3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD
8 2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD
9 44 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