Optimal parallel clustering algorithms on a reconfigurable array of processors with wider bus networks
Clustering techniques are usually used in pattern recognition, image segmentation and object detection. For N patterns and k centers each with M features, in this paper, we first design an O(kM) time optimal parallel algorithm for one pass process of clustering with the k-means method on a linear array of processors with a wider bus network using N1+1/epsilon processors with one bus network, where c is any constant and c greater than or equal to 1. Then, based on the proposed algorithm, two O(k) and O(1) time optimal parallel clustering algorithms are also derived using MN1+1/epsilon and kMN(1+1/epsilon) processors with M row and MN row bus networks, respectively. These results improve the best known bounds and achieve cost optimal in their time and processor complexities. (C) 1999 Elsevier Science B.V. All rights reserved.
pattern recognition parallel algorithm k-means method cluster analysis pattern cluster image processing array of processors with a wider bus network (rapwbn)