We propose a parallel graph-based data clustering algorithm using CUDA GPU, based on exact clustering of the minimum spanning tree in terms of a minimum isoperimetric criteria. We also provide a comparative performance analysis of our algorithm with other related ones which demonstrates the general superiority of this parallel algorithm over other competing algorithms in terms of accuracy and speed.
Various algorithms and strategies have been proposed to improve the computational performance of data clustering and its applications to image segmentation, signal processing and etc. In this manner, some attempts have been devoted to develop parallel adaptations of the well-known methods. K-means is one of the most popular algorithm in data clustering literature. Firstly, Stoffel and Belkoniene @cite_15 developed some parallel techniques for this algorithm. Afterwards, many attempts was devoted to design and implement the parallel version for k-means in the large data sets (e.g. see @cite_5 and @cite_4 ).
@cite_5 @cite_15 @cite_4
1870625491 199449237
To cluster increasingly massive data sets that are common today in data and text mining, we propose a parallel implementation of the k-means clustering algorithm based on the message passing model. The proposed algorithm exploits the inherent data-parallelism in the kmeans algorithm. We analytically show that the speedup and the scaleup of our algorithm approach the optimal as the number of data points increases. We implemented our algorithm on an IBM POWERparallel SP2 with a maximum of 16 nodes. On typical test data sets, we observe nearly linear relative speedups, for example, 15.62 on 16 nodes, and essentially linear scaleup in the size of the data set and in the number of clusters desired. For a 2 gigabyte test data set, our implementation drives the 16 node SP2 at more than 1.8 gigaflops. This paper describes the realization of a parallel version of the k h-means clustering algorithm. This is one of the basic algorithms used in a wide range of data mining tasks. We show how a database can be distributed and how the algorithm can be applied to this distributed database. The tests conducted on a network of 32 PCs showed for large data sets a nearly ideal speedup.