Exploiting parallelism to support scalable hierarchical clustering

Rebecca J. Cathey, Eric C. Jensen, Steven M. Beitzel, Ophir Frieder and David Grossman

Journal of the American Society for Information Science and Technology, 2007, vol. 58, issue 8, 1207-1221

Abstract: 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.

Date: 2007
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/asi.20596

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:jamist:v:58:y:2007:i:8:p:1207-1221

Ordering information: This journal article can be ordered from
https://doi.org/10.1002/(ISSN)1532-2890

Access Statistics for this article

More articles in Journal of the American Society for Information Science and Technology from Association for Information Science & Technology
Bibliographic data for series maintained by Wiley Content Delivery ().