DocumentCode :
2526909
Title :
SIMD algorithms for single link and complete link pattern clustering
Author :
Arumugavelu, S. ; Ranganathan, N.
Author_Institution :
Dept. of Comput. Sci. & Eng., Univ. of South Florida, Tampa, FL, USA
Volume :
4
fYear :
1996
fDate :
25-29 Aug 1996
Firstpage :
625
Abstract :
In this paper, new parallel algorithms for single and complete link hierarchical agglomerative clustering are presented. The parallel algorithms have been mapped on a SIMD machine model with a linear interconnection network. The model consists of a linear array of N PE´s, where N is the number of patterns, interfaced with a global host machine and the interconnection network provides inter-PE and PE-to-host/host-to-PE communication. The proposed algorithms are faster than previously known algorithms for hierarchical clustering. For clustering a data set with N patterns, using N PE´s, the computation time for the single link clustering algorithm is shown to be O(NlogN) and that for the complete link clustering algorithm is shown to be O(N 2). The parallel algorithms have been verified through simulations on the Intel´s iPSC/2 concurrent supercomputer
Keywords :
computational complexity; parallel processing; pattern recognition; Intel; SIMD machine model; complete link pattern clustering; hierarchical agglomerative clustering; iPSC/2 concurrent supercomputer; linear interconnection network; parallel algorithms; single link pattern clustering; Algorithm design and analysis; Clustering algorithms; Computational modeling; Computer science; Concurrent computing; Microelectronics; Nearest neighbor searches; Parallel algorithms; Pattern clustering; Supercomputers;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Pattern Recognition, 1996., Proceedings of the 13th International Conference on
Conference_Location :
Vienna
ISSN :
1051-4651
Print_ISBN :
0-8186-7282-X
Type :
conf
DOI :
10.1109/ICPR.1996.547640
Filename :
547640
Link To Document :
بازگشت