Efficient Physical Organization of R-Trees Using Node Clustering

Abstract

R-Tree is a multidimensional indexing structure that forms basis for all the multidimensional indexing structures based on data partitioning. A number of attempts have been made in the past to improve the performance of R-Tree by manipulating the tree parameters and the data parameters. But hardly any attempt had been made to use external parameters such as disk parameters to enhance the performance. This work attempts to improve the performance of R-Tree by efficiently clustering the nodes into input-output units of the hard disk with in the constraint that the independence between the logical and physical organization of the R-Tree should be preserved. Moreover, to preserve the structural and functional properties of R-Tree at any point in the process of clustering, this paper introduces a concept called ‘controlled duplication’. Extensive experiments were conducted and the results are tabulated. The improvements are significant and open more avenues for exploration.