| |
HP Labs Technical Reports
Click here for full text:
Accurate Recasting of Parameter Estimation Algorithms Using Sufficient Statistic for Efficient Parallel Speed-up--Demonstrated for Center-Based Data Clustering Algorithms
Zhang, Bin; Hsu, Meichun; Forman, George
HPL-2000-94
Keyword(s): parallel algorithms; data mining; data clustering; K- Means; K-Harmonic Means; Expectation-Maximization; speed-up; scale-up
Abstract: Fueled by advances in computer technology and online business, data collection is rapidly accelerating, as well as the importance of its analysis--data mining. Increasing database sizes strain the scalability of many data mining algorithms. Data clustering is one of the fundamental techniques in data mining solutions. The many clustering algorithms developed face new challenges with growing data sets. Algorithms with quadratic or higher computational complexity, such as agglomerative algorithms, drop out quickly. More efficient algorithms, such as K-Means EM with linear cost per iteration, still need work to scale up to large data sets. This paper shows that many parameter estimation algorithms, including K-Means, K-Harmonic Means and EM, can be recast without approximation in terms of Sufficient Statistics, yielding a superior speed-up efficiency. Estimates using today's workstations and local area network technology suggest efficient speed-up to several hundred computers, leading to effective scale-up for clustering hundreds of gigabytes of data. Implementation of parallel clustering has been done in a parallel programming language, ZPL. Experimental results show above 90% utilization.
10 Pages
Back to Index
|
