Journal of Computer Science

Efficient Physical Organization of R-Trees Using Node Clustering

F. Sagayaraj Francis and P. Thambidurai

DOI : 10.3844/jcssp.2007.506.514

Journal of Computer Science

Volume 3, Issue 7

Pages 506-514


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.


© 2007 F. Sagayaraj Francis and P. Thambidurai. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.