Designing scalable and efficient parallel clustering algorithms on arrays with reconfigurable optical buses

摘要

Clustering is a part of data analysis that is required in many fields. In most applications such as unsupervised pattern recognition and image segmentation, the number of patterns may be very large. Therefore, designing fast and processor efficient parallel algorithms for clustering is definitely of fundamental importance. In this paper, for N patterns and K centers each with M features, we propose several efficient and scalable parallel algorithms for squared error clustering on the arrays with reconfigurable optical buses with various number of processors. Based on the advantages of both optical transmission and electronic computation, the proposed algorithms can be run in O((K/p)logN), O(logN), O((KNM/pqr)+logr+logq), O(K/p), O(1), O(K) and O(KM) time using p×M×N/logN, K×M×N/logN, p×q×r, p×M×N1+1/ϵ, K×M×N1+1/ϵ, M×N1+1/ϵ and N1+1/ϵ processors, for some constant ϵ and ϵ≥1, respectively. These results are more efficient and scalable than the previously known algorithms.