Bibliographic Details
| Title: |
pPOP: Fast yet accurate parallel hierarchical clustering using partitioning |
| Authors: |
Dash, Manoranjan1 asmdash@ntu.edu.sg, Petrutiu, Simona2, Scheuermann, Peter2 |
| Source: |
Data & Knowledge Engineering. Jun2007, Vol. 61 Issue 3, p563-578. 16p. |
| Subjects: |
POP (Computer program language), Algorithms, Motherboards, Parallel algorithms, Computer programming, Computer storage devices, Database management software, Electronic data processing, Information storage & retrieval systems |
| Abstract: |
Abstract: Hierarchical agglomerative clustering (HAC) is very useful but due to high CPU time and memory complexity its practical use is limited. Earlier, we proposed an efficient partitioning – partially overlapping partitioning (POP) – based on the fact that in HAC small and closely placed clusters are agglomerated initially, and only towards the end larger and distant clusters are agglomerated. Here, we present the parallel version of POP, pPOP. Theoretical analysis shows that, compared to the existing algorithms, pPOP achieves CPU time speed-up and memory scale-down of O(c) without compromising accuracy where c is the number of cells in the partition. A shared memory implementation shows that pPOP outperforms existing algorithms significantly. [Copyright &y& Elsevier] |
|
Copyright of Data & Knowledge Engineering is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
