Database Paper Browser

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
1086
Venue
PODS
Year
1996
Pagerank
0.00011535609
Overall Rank
1,519 | 89.45%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank Citing Paper Year Venue Pagerank
523 Recovering Information from Summary Data 1997 VLDB 0.00021101376
1,568 Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions 2005 VLDB 0.0001131667
1,808 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010476269
1,924 Reverse kNN Search in Arbitrary Dimensionality 2004 VLDB 0.00010075677
2,056 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.6692561e-05
2,371 Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data 2007 VLDB 8.9443366e-05
2,844 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.0308994e-05
3,278 Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data 2002 SIGMOD 7.2858181e-05
3,523 Efficient Proximity Detection among Mobile Users via Self-Tuning Policies 2010 VLDB 7.0082046e-05
3,540 Approximation Techniques for Spatial Data 2004 SIGMOD 6.9922652e-05
3,634 Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases 2008 SIGMOD 6.8949444e-05
4,880 Reverse Spatial and Textual k Nearest Neighbor Search 2011 SIGMOD 5.8526687e-05
6,055 Spatial Indexing in Microsoft SQL Server 2008 2008 SIGMOD 5.2297716e-05
6,170 Spatial Join Selectivity Using Power Laws 2000 SIGMOD 5.1708554e-05
6,707 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 4.9500448e-05
6,766 Workload-Aware Indexing of Continuously Moving Objects 2009 VLDB 4.9280867e-05
7,263 Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges 2017 SIGMOD 4.7789103e-05
7,727 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 4.6616221e-05
7,784 Authenticated Online Data Integration Services 2015 SIGMOD 4.6472451e-05
8,704 Incremental Partitioning for Efficient Spatial Data Analytics 2022 VLDB 4.4596039e-05
9,173 Similarity Query Processing Using Disk Arrays 1998 SIGMOD 4.3807204e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
56 Direct Spatial Search on Pictorial Databases Using Packed R-trees 1985 SIGMOD 0.00065500256
356 Hilbert R-tree: An Improved R-tree Using Fractals 1994 VLDB 0.00026091196
1,009 The BANG file: a new kind of grid file 1987 SIGMOD 0.00014658958
1,111 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.0001389881
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05
2,144 The LSD tree: spatial access to multidimensional point and non-point objects 1989 VLDB 9.4375327e-05
3,111 Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees 1995 SIGMOD 7.5445257e-05
6,073 Window Query-Optimal Clustering of Spatial Objects 1995 PODS 5.2215154e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,245 Parallel R-trees 1992 SIGMOD 9.2048202e-05
1,111 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.0001389881
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032118946
2,033 Analysis Of Object Oriented Spatial Access Methods 1987 SIGMOD 9.7315522e-05
1,055 The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries 2003 VLDB 0.00014391376
3,259 A Revised R*-tree in Comparison with Related Index Structures 2009 SIGMOD 7.3101573e-05
1,808 A Cost Model for Similarity Queries in Metric Spaces 1998 PODS 0.00010476269
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
147 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00041201518
7,518 A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing 2005 VLDB 4.7135369e-05