Parallel M-tree Based on Declustering Metric Objects using K-medoids Clustering

A new declustering data algorithm based on k-medoids clustering is presented in this paper. Since the k-medoids clustering algorithm is able to discover distribution of the objects, the proposed method uses it to figure out which objects are neighboring to be distributed into different disks. Compared with the existing algorithms, our algorithm has the advantages of taking the overall proximities of the whole dataset into consideration. With this new declustering algorithm, we give a method to build a parallel M-tree in a general PC server cluster system. The results of experiments have demonstrated that our declustering algorithm can achieve the static and dynamic load balance of the multiple disks, and the parallel M-tree has a better performance of k-NN query than the sequential version.