DBScholar

Back to papers

A Model for the Prediction of R-tree Performance

Summary: Analytical cost model predicting R-tree (and variants) disk-accesses for range queries using only dataset statistics (volume and spatial density), so applicable before index construction. Validated on synthetic/real data with ~10–15% error, useful for spatial query optimization. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1085
Venue
PODS
Year
1996
Pagerank
0.0001098638
Overall Rank
1,373 | 90.59%
DOI
10.1145/237661.237705

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{theodoridis_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{A Model for the Prediction of R-tree Performance}},
        url = {https://dl.acm.org/doi/10.1145/237661.237705},
        doi = {10.1145/237661.237705},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Theodoridis, Yannis and Sellis, Timos},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank Citing Paper Year Venue Pagerank
952 Recovering Information from Summary Data 1997 VLDB 0.00013010681
1,486 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010625076
1,612 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010218134
2,101 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.1657486e-05
2,127 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.127762e-05
2,281 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.8129279e-05
2,827 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 8.0831263e-05
3,139 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.7188328e-05
3,217 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.6314544e-05
3,703 Approximation Techniques for Spatial Data 2004 SIGMOD 7.1829776e-05
4,711 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.5506926e-05
5,623 Efficient Proximity Detection among Mobile Users via Self-Tuning Policies 2010 VLDB 6.1453429e-05
5,648 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 6.1351417e-05
5,857 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 6.0644613e-05
5,932 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 6.0369275e-05
6,458 Workload-Aware Indexing of Continuously Moving Objects 2009 VLDB 5.8736158e-05
7,576 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 5.593012e-05
7,744 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.5541724e-05
7,879 Authenticated Online Data Integration Services 2015 SIGMOD 5.5245691e-05
8,644 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.3934068e-05
9,417 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.2740525e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.001157935
28 Nearest Neighbor Queries 1995 SIGMOD 0.00052102434
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.0003221055
329 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00021068647
1,032 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012530965
1,129 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00012061727
1,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.6928497e-05
1,877 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.5658249e-05
3,290 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.5531472e-05
6,089 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.9806097e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,341 Parallel R-trees 1992 SIGMOD
2 1,129 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS
3 2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD
4 1,814 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
5 957 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB
6 2,974 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 2,101 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS
8 4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD
9 145 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD
10 7,939 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB