Efficient Parallel Algorithms for Hierarchical Clustering on Arrays with Reconfigurable Optical Buses

✍ Scribed by Chin-Hsiung Wu; Shi-Jinn Horng; Horng-Ren Tsai

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 225 KB
• Volume: 60
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1644

✦ Synopsis

Clustering is a basic operation in image processing and computer vision, and it plays an important role in unsupervised pattern recognition and image segmentation. While there are many methods for clustering, the single-link hierarchical clustering is one of the most popular techniques. In this paper, with the advantages of both optical transmission and electronic computation, we design efficient parallel hierarchical clustering algorithms on the arrays with reconfigurable optical buses (AROB). We first design three efficient basic operations which include the matrix multiplication of two N_N matrices, finding the minimum spanning tree of a graph with N vertices, and identifying the connected component containing a specified vertex. Based on these three data operations, an O(log N) time parallel hierarchical clustering algorithm is proposed using N 3 processors. Furthermore, if the connectivity of the AROB with four-port connection is allowed, two constant time clustering algorithms can be also derived using N 4 and N 3 processors, respectively. These results improve on previously known algorithms developed on various parallel computational models.