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.0001076417
Overall Rank
1,405 | 90.56%
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
967 Recovering Information from Summary Data 1997 VLDB 0.00012794553
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.00010396565
1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010201796
2,079 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.0775779e-05
2,162 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.935022e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6708797e-05
2,893 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 7.9019071e-05
3,192 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5512396e-05
3,253 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.4900624e-05
3,758 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0437238e-05
4,797 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.4113285e-05
5,749 Efficient Proximity Detection among Mobile Users via Self-Tuning Policies 2010 VLDB 6.0076091e-05
5,779 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 5.9976039e-05
5,963 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9330399e-05
6,052 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.9028248e-05
6,578 Workload-Aware Indexing of Continuously Moving Objects 2009 VLDB 5.744723e-05
7,723 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 5.4675199e-05
7,904 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4295914e-05
8,046 Authenticated Online Data Integration Services 2015 SIGMOD 5.4007578e-05
8,809 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2724071e-05
9,597 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1557462e-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.001992968
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011405675
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051312804
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031645463
335 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020660268
1,055 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012266704
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011848523
1,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4871409e-05
1,903 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.4032472e-05
3,347 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3933163e-05
6,216 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.847583e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,388 Parallel R-trees 1992 SIGMOD
2 1,142 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,861 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD
5 985 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB
6 3,034 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 2,079 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,107 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB