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
h6543e7c2efc42784
Venue
PODS
Year
1996
Pagerank
0.00010725178
Overall Rank
1,412 | 90.54%
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
971 Recovering Information from Summary Data 1997 VLDB 0.00012748313
1,520 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010358287
1,574 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010164216
2,080 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.058838e-05
2,176 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9031141e-05
2,310 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6493038e-05
2,904 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 7.8723013e-05
3,203 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5227628e-05
3,267 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.46539e-05
3,765 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0178846e-05
4,821 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.3876508e-05
5,760 Efficient Proximity Detection among Mobile Users via Self-Tuning Policies 2010 VLDB 5.9855728e-05
5,796 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 5.9752115e-05
5,977 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9106575e-05
6,068 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.8805774e-05
6,591 Workload-Aware Indexing of Continuously Moving Objects 2009 VLDB 5.7231529e-05
7,742 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 5.4468611e-05
7,924 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4090777e-05
8,058 Authenticated Online Data Integration Services 2015 SIGMOD 5.3824183e-05
8,834 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2524856e-05
9,631 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1362663e-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.0019892478
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011386412
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051134355
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031562001
338 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.0002058961
1,060 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012222117
1,143 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011810737
1,869 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4516156e-05
1,915 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.368237e-05
3,354 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3666926e-05
6,231 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.8255825e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,400 Parallel R-trees 1992 SIGMOD
2 1,143 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,869 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
5 990 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB
6 3,044 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 2,080 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 146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD
10 8,132 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB