A parallel hierarchical clustering algorithm for PCs cluster system

The efficiency of clustering algorithms is strongly needed with very large databases and high-dimensional data types. As a solution, parallel algorithms can be used to provide powerful computing ability. PCs cluster system is one of low-cost general-purpose parallel computing systems. In this paper, we first theoretically analyze the idea of adopting data parallelism when designing a parallel clustering algorithm for PCs cluster systems, including analysis of speedup and selection of communication schemes. We then present a parallel hierarchical clustering algorithm called PARC. Experiment results demonstrate the correctness of the theoretical analysis and show that in general, PARC obtains as good quality of clustering as linear clustering algorithms, while communication time is considerably improved.