An Adaptive Parallel Hierarchical Clustering Algorithms without Memory Conflicts

论文摘要

Clustering of data has numerous applications and has been studied extensively. It is very important in Bio-informatics and data mining. Though many parallel algorithms have been designed, most of algorithms use the CRCW-PRAM or CREW-PRAM models of computing. This paper proposes a parallel EREW deterministic algorithm for hierarchical clustering. Based on algorithms of complete graph and Euclidean minimum spanning tree, the proposed algorithms can cluster n objects with O（p） processors in O（n2/p） time where 1≤p≤n/logn. Performance comparisons show that our algorithm is the first algorithm that is both without memory conflicts and adaptive.

论文目录

• Abstract
• Chapter 1 Introduction
• 1.1 Introduction
• 1.2 What is Parallel Computing
• 1.3 What’s Parallel Computer
• 1.4 What is Parallel Programming
• 1.5 What is the Clustering
• Chapter 2 Preliminaries
• 2.1 Models Of Computing
• 2.2 Hierarchical Clustering
• 2.3 Distributed Computing and Super Computers
• 2.3.1 Distributed Computing
• 2.3.2 Super Computers
• Chapter 3 The Proposed Algorithms
• 3.1 Introduction
• 3.2 Construct a Complete Graph in Parallel
• 3.3 Generatic Of MST
• 3.4 Pruning edges and finding connected compenents
• 3.5 The proposed parallel hierarchical clustering algorithm
• Chapter 4 Comparison And Conclusion
• 4.1 Performance comparisons
• 4.2 Conclusions
• 4.3 Future Plan
• Acknowledgements
• References