Title :
A parallel hierarchical clustering algorithm based on PRAM model
Author :
Zhou, Yantao ; Wu, Zhengguo
Author_Institution :
Coll. of Electr. & Inf. Eng., Hunan Univ., Changsha, China
Abstract :
An adaptive parallel algorithm for hierarchical clustering based on PRAM model was presented. Performing the data preprocessing depended on ldquo90-10rdquo rule to decrease the numbers of data set, performing the parallel algorithm for creating Euclid Minimum Spanning Trees on absolute graph, performing the algorithm for finding the disjoining strategies and non-collision memory, data set was clustered optimizedly. Data set was clustered on the conditions of non-collision memory, lowest-cost and weakest PRAM-EREW model. N data sets were clustered in O((lambdan)2/p) time (0.1leslambdales0.3) performing this algorithm on p processors (1lesplesn/log(n)). The parallel clustering algorithm based on PRAM model is an adaptive non-collision memory parallel hierarchical clustering algorithm. The calculating time will be greatly reduced after original inputing data are effectually preprocessed through improved preprocessing methods of this thesis.
Keywords :
computational complexity; parallel algorithms; pattern clustering; storage management; trees (mathematics); Euclid minimum spanning tree; PRAM-EREW model; absolute graph; adaptive noncollision memory parallel hierarchical clustering algorithm; data preprocessing; disjoin strategy; Clustering algorithms; Computer networks; Concurrent computing; Data preprocessing; Distributed computing; Educational institutions; Electronic mail; Parallel algorithms; Phase change random access memory; Read-write memory; PRAM model; clustering algorithm; hierarchica lclustering; parallel computation;
Conference_Titel :
Cyber-Enabled Distributed Computing and Knowledge Discovery, 2009. CyberC '09. International Conference on
Conference_Location :
Zhangijajie
Print_ISBN :
978-1-4244-5218-7
Electronic_ISBN :
978-1-4244-5219-4
DOI :
10.1109/CYBERC.2009.5342145
