A parallel clustering algorithm on the star graph and its performance

In this paper, a parallel algorithm is presented for data clustering on a multicomputer with star topology. This algorithm is fast and requires a small amount of memory per processing element, which makes it even suitable for SIMD implementation. The proposed parallel algorithm completes in O(K+S2−T2)O(K+S2−T2) steps for a clustering problem of NN data patterns with MM features per pattern and KK clusters where SS and TT are the minimum numbers such that NM≤S!NM≤S! and KM≤T!KM≤T!, on the SS-dimensional star graph.