Research Article Open Access

Efficient Physical Organization of R-Trees Using Node Clustering

F. Sagayaraj Francis and P. Thambidurai


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.

Journal of Computer Science
Volume 3 No. 7, 2007, 506-514


Submitted On: 20 May 2007 Published On: 31 July 2007

How to Cite: Francis, F. S. & Thambidurai, P. (2007). Efficient Physical Organization of R-Trees Using Node Clustering. Journal of Computer Science, 3(7), 506-514.

  • 0 Citations



  • multidimensional indexing
  • R-Tree
  • physical organization
  • clustering
  • hard disk
  • organizational independence
  • controlled duplication