Optimizing storage utilization in R-tree dynamic index structure for spatial databases

Spatial databases have been increasingly and widely used in recent years. T he R-tree proposed by Guttman is probably the most popular dynamic index st ructure for efficiently retrieving objects from a spatial database accordin g to their spatial locations. However, experiments show that only about 70% storage utilization can be achieved in Guttman's R-tree and its variants. In this paper, we propose a compact R-tree structure which can achieve almo st 100% storage utilization. Our experiments also show that the search perf ormance of compact R-trees is very competitive as compared to Guttman's R-t rees. In addition, the overhead cost of building a compact R-tree is much l ower than that of a Guttman's R-tree because the frequency of node splittin g is reduced significantly. (C) 2001 Elsevier Science Inc. All rights reser ved.