R Tree Index Optimization

Abstract: "The optimization of spatial indexing is an increasingly important issue considering the fact that spatial databases, in such diverse areas as geographical, CAD/CAM and image applications, are growing rapidly in size and often contain on the order of millions of items or more. This necessitates the storage of the index on disk, which has the potential of slowing down the access time significantly. In this paper, we discuss ways of minimizing the disk access frequency by grouping together data items which are close to one another in the spatial domain ('packing'). The data structure which we seek to optimize here is the R- tree for a given set of data objects. Existing methods of building an R- tree index based on space-filling curves (Peano, Hilbert) are computationally cheap, but they do not preserve spatial locality well, in particular when dealing with higher-dimensional data of non-zero extent. On the other hand, existing methods of packing based on all dimensions of the data, such as the several proposed dynamic R-tree insertion algorithms, do not take advantage of the fact that all the data objects are known beforehand. Furthermore, they are essentially serial in nature. In this paper, we regard packing as an optimization problem and propose an iterative method of finding a close-to-optimal solution to the packing of a given set of spatial objects in D dimensions. The method achieves a high degree of parallelism by constructing the R-tree bottom-up. In experiments on data of various dimensionalities and distributions, we have found that the proposed method can significantly improve on the packing performance of the R* insertion algorithm and the Hilbert curve. It is shown that the improvements increase with the skewness of the data and, in some cases, can even amount to an order of magnitude in terms of decreased response time."