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.00010759378
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
969 Recovering Information from Summary Data 1997 VLDB 0.00012788914
1,518 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.0001039208
1,571 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010197322
2,077 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 9.0758123e-05
2,164 Selectivity Estimation in Spatial Databases 1999 SIGMOD 8.9309999e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6685874e-05
2,893 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 7.8981754e-05
3,193 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 7.5476762e-05
3,254 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.487573e-05
3,761 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0403969e-05
4,799 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 6.4084993e-05
5,750 Efficient Proximity Detection among Mobile Users via Self-Tuning Policies 2010 VLDB 6.0047651e-05
5,781 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 5.9947648e-05
5,965 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.9302348e-05
6,054 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.9000316e-05
6,582 Workload-Aware Indexing of Continuously Moving Objects 2009 VLDB 5.7421081e-05
7,729 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 5.4649316e-05
7,908 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4270211e-05
8,052 Authenticated Online Data Integration Services 2015 SIGMOD 5.3982012e-05
8,817 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 5.2699112e-05
9,605 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 5.1533056e-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.0019923528
4 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0011402175
28 Nearest Neighbor Queries 1995 SIGMOD 0.00051292389
116 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00031633451
336 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00020652147
1,055 The BANG file: a new kind of grid file 1987 SIGMOD 0.00012261335
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011843746
1,862 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.4827102e-05
1,904 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.3990319e-05
3,346 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.3899839e-05
6,219 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.844834e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,390 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,862 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,035 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD
7 2,077 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,114 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB