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/ε processors with one bus network, where c is any constant and c≥1. Then, based on the proposed algorithm, two O(k) and O(1) time optimal parallel clustering algorithms are also derived using MN1+1/ε and kMN1+1/ε 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.