Cost Model of R-tree and Algorithmic Optimization

We present a cost model for predicting the performance of R-tree and its variants.Optimization based on the cost model can be applied to R-tree construction.We construct a new R-tree variant named CR^*-tree using this cost model.Experiment results show that the relative error of the cost model is around 12.6%,and the performance for querying CR^*-tree has been improved 4.25% in contrast with R^*-tree’s.