On Sat, Jun 19, 1999 at 09:12:11PM +0000, Bernard Frankpitt wrote:
> 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
>
Hmm, a quick Google search for these two authors hit on a great index server
in Germany:
http://www.informatik.uni-trier.de/~ley/db/index.html
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/f/Faloutsos:Christos.htm
And that paper in particular:
http://www.informatik.uni-trier.de/~ley/db/conf/pods/pods94-4.html
Which gives an abstract, access to an electronic version (ACS membership
required) and a cite for a more recent (1997) journal paper.
HTH,
Ross
--
Ross J. Reedstrom, Ph.D., <reedstrm@rice.edu>
NSBRI Research Scientist/Programmer
Computer and Information Technology Institute
Rice University, 6100 S. Main St., Houston, TX 77005