An Adaptive Parallel Hierarchical Clustering Algorithms Without Memory Conflicts

Clustering of data has numerous applications and has been studied extensively. It is very important in Bio-informatics and data mining. Though many parallel algorithms have been designed, most of algorithms use the CRCW-PRAM or CREW-PRAM models of computing. This paper proposes a parallel EREW deterministic algorithm for hierarchical clustering. Based on algorithms of complete graph and Euclidean minimum spanning tree, the proposed algorithms can cluster n objects with O(p) processors in O(n~2/p) time where 1≤p≤n/logn. Performance comparisons show that our algorithm is the first algorithm that is both without memory conflicts and adaptive.