A model for the prediction of R-tree performance
Yannis Theodoridis, Timos Sellis · 1996
In this paper we present an analytical model that predicts the performance of R-trees (and its variants) when a range query needs to be answered.The cost model uses knowledge of the dataset only, i.e., the proposed formula that estimates the number of disk accesses is a hmction of data properties, namely, the amount of data and their density in the work space.In other words, the proposed model is applicable even before the construction of the R-tree index, a fact that makes it a useful tool for dynamic spatial databases.Several experiments on synthetic and real datasets show that the proposed analytical model is very accurate, the relative error being usually around 10%-15%, for uniform and non-uniform distributions.We believe that this error is involved with the gap between efficient R-tree variants, like the R*-tree, and an optimum, not implemented yet, method.Our work extends previous research concerning R-tree analysis and constitutes a useful tool for spatial query optimizers that need to evaluate the cost of a complex spatial query and its execution procedure.