Parallel clustering algorithms on a reconfigurable array of processors with wider bus networks
Horng-Ren Tsai, Shi-Jinn Horng, Shun-Shan Tsai, Shung-Shing Lee, Tzong‐Wann Kao, Chia-Ho Chen · 2002
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 N/sup 1+1/c/ processors with one bus network, where c is any constant and c/spl ges/1. Then, based on the proposed algorithm, two O(k) and O(1) time optimal parallel clustering algorithms are also derived using MN/sup 1+1/c/ and kMN/sup 1+1/c/ 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.