Portal de Periódicos da CAPES

Parallel clustering algorithms

1989; Elsevier BV; Volume: 11; Issue: 3 Linguagem: Inglês

10.1016/0167-8191(89)90036-7

1872-7336

Xiaobo Li, Zhixi Fang,

Advanced Data Compression Techniques

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2n patterns and M = 2m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN2) of the uniprocessor algorithm to O(nN) with MN processors.