Exploiting parallelism to support scalable hierarchical clustering.
A distributed memory parallel version of the group average hierarchical agglomerative clustering algorithm is proposed to enable scaling the document clustering problem to large collections. Using standard message passing operations reduces interprocess communication while maintaining efficient load...
| Publicado en: | Journal of the American Society for Information Science & Technology Vol. 58; no. 8; pp. 1207 - 1222 |
|---|---|
| Autores principales: | , , , , |
| Formato: | algorithm equations & formulas research tables/charts Journal Article |
| Publicado: |
Wiley-Blackwell
Jun2007
|
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=ccm&AN=105930009&site=ehost-live header: @attributes: shortDbName: ccm uiTerm: 105930009 longDbName: CINAHL Complete uiTag: AN controlInfo: bkinfo: dissinfo: jinfo: jid: 15322882 IGD jtl: Journal of the American Society for Information Science & Technology issn: 15322882 maglogo: Y pubinfo: dt: Jun2007 vid: 58 iid: 8 pid: 480 pub: Wiley-Blackwell place: Malden, Massachusetts artinfo: ui: 105930009 105930009 2009600989 10.1002/asi.20596 105930009 ppf: 1207 ppct: 15 formats: tig: atl: Exploiting parallelism to support scalable hierarchical clustering. aug: au: Cathey RJ Jensen EC Beitzel SM Frieder O Grossman D affil: Information Retrieval Laboratory, Dept of Computer Science, Illinois Institute of Technology, 10W 31st St, Chicago, IL 60616; cathey@ir.iit.edu sug: subj: Algorithms Information Retrieval Methods Newspapers Paired T-Tests Human ab: A distributed memory parallel version of the group average hierarchical agglomerative clustering algorithm is proposed to enable scaling the document clustering problem to large collections. Using standard message passing operations reduces interprocess communication while maintaining efficient load balancing. In a series of experiments using a subset of a standard Text REtrieval Conference (TREC) test collection, our parallel hierarchical clustering algorithm is shown to be scalable in terms of processors efficiently used and the collection size. Results show that our algorithm performs close to the expected O(n2/p) time on p processors rather than the worst-case O(n3/p) time. Furthermore, the O(n2/p) memory complexity per node allows larger collections to be clustered as the number of nodes increases. While partitioning algorithms such as k-means are trivially parallelizable, our results confirm those of other studies which showed that hierarchical algorithms produce significantly tighter clusters in the document clustering task. Finally, we show how our parallel hierarchical agglomerative clustering algorithm can be used as the clustering subroutine for a parallel version of the buckshot algorithm to cluster the complete TREC collection at near theoretical runtime expectations. pubtype: Academic Journal doctype: algorithm equations & formulas research tables/charts Journal Article ougenre: Article language: English refInfo: holdings: @attributes: islocal: N |
|---|