I read through some of the papers about R-trees and GIST about a year
ago,
and it seems that estimating costs for R-tree searches (and GIST
searches) is
not so straightforward as B-Trees.
Hellerstein et al. 1995 write "...currently such estimates are reasonably accurate for B+ trees
and less so for R-Trees. Recently, some work on R-tree cost
estimation has been done by [FK94], but more work is required to bring
this to bear on GISTs in general...."
The reference that they give is
[FK94] Christos Faloutsos and Ibrahim Kamel. "Beyond Uniformity and
Independence: Analysis of R-trees using the concept of fractal
dimension.
Proc. 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database
Systems, pp 4--13, Minneapolis, May 1994
I don't have the Faloustos paper. The R-tree code authors, and the GIST
authors just used the B-Tree code as an expedient solution.
Bernie Frankpitt
