Parallel hierarchical clustering on shared memory platforms

William Hendrix; Md Mostofa Ali Patwary; Ankit Agrawal; Wei Keng Liao; Alok Choudhary

doi:10.1109/HiPC.2012.6507511

Parallel hierarchical clustering on shared memory platforms

William Hendrix, Md Mostofa Ali Patwary, Ankit Agrawal, Wei Keng Liao, Alok Choudhary

Department of Computer Science

Northwestern University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

19 Scopus citations

Abstract

Hierarchical clustering has many advantages over traditional clustering algorithms like k-means, but it suffers from higher computational costs and a less obvious parallel structure. Thus, in order to scale this technique up to larger datasets, we present SHRINK, a novel shared-memory algorithm for single-linkage hierarchical clustering based on merging the solutions from overlapping sub-problems. In our experiments, we find that SHRINK provides a speedup of 18-20 on 36 cores on both real and synthetic datasets of up to 250,000 points. Source code for SHRINK is available for download on our website, http://cucis.ece.northwestern.edu.

Original language	English
Title of host publication	2012 19th International Conference on High Performance Computing, HiPC 2012
DOIs	https://doi.org/10.1109/HiPC.2012.6507511
State	Published - 2012
Event	2012 19th International Conference on High Performance Computing, HiPC 2012 - Pune, India Duration: 18 Dec 2012 → 21 Dec 2012

Publication series

Name	2012 19th International Conference on High Performance Computing, HiPC 2012

Conference

Conference	2012 19th International Conference on High Performance Computing, HiPC 2012
Country/Territory	India
City	Pune
Period	18/12/12 → 21/12/12

Access to Document

10.1109/HiPC.2012.6507511

Cite this

@inproceedings{78c45e2a792440548e84bac3ed97a573,

title = "Parallel hierarchical clustering on shared memory platforms",

abstract = "Hierarchical clustering has many advantages over traditional clustering algorithms like k-means, but it suffers from higher computational costs and a less obvious parallel structure. Thus, in order to scale this technique up to larger datasets, we present SHRINK, a novel shared-memory algorithm for single-linkage hierarchical clustering based on merging the solutions from overlapping sub-problems. In our experiments, we find that SHRINK provides a speedup of 18-20 on 36 cores on both real and synthetic datasets of up to 250,000 points. Source code for SHRINK is available for download on our website, http://cucis.ece.northwestern.edu.",

author = "William Hendrix and {Ali Patwary}, {Md Mostofa} and Ankit Agrawal and Liao, {Wei Keng} and Alok Choudhary",

year = "2012",

doi = "10.1109/HiPC.2012.6507511",

language = "English",

isbn = "9781467323703",

series = "2012 19th International Conference on High Performance Computing, HiPC 2012",

booktitle = "2012 19th International Conference on High Performance Computing, HiPC 2012",

note = "2012 19th International Conference on High Performance Computing, HiPC 2012 ; Conference date: 18-12-2012 Through 21-12-2012",

}

Hendrix, W, Ali Patwary, MM, Agrawal, A, Liao, WK & Choudhary, A 2012, Parallel hierarchical clustering on shared memory platforms. in 2012 19th International Conference on High Performance Computing, HiPC 2012., 6507511, 2012 19th International Conference on High Performance Computing, HiPC 2012, 2012 19th International Conference on High Performance Computing, HiPC 2012, Pune, India, 18/12/12. https://doi.org/10.1109/HiPC.2012.6507511

Parallel hierarchical clustering on shared memory platforms. / Hendrix, William; Ali Patwary, Md Mostofa; Agrawal, Ankit et al.
2012 19th International Conference on High Performance Computing, HiPC 2012. 2012. 6507511 (2012 19th International Conference on High Performance Computing, HiPC 2012).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Parallel hierarchical clustering on shared memory platforms

AU - Hendrix, William

AU - Ali Patwary, Md Mostofa

AU - Agrawal, Ankit

AU - Liao, Wei Keng

AU - Choudhary, Alok

PY - 2012

Y1 - 2012

N2 - Hierarchical clustering has many advantages over traditional clustering algorithms like k-means, but it suffers from higher computational costs and a less obvious parallel structure. Thus, in order to scale this technique up to larger datasets, we present SHRINK, a novel shared-memory algorithm for single-linkage hierarchical clustering based on merging the solutions from overlapping sub-problems. In our experiments, we find that SHRINK provides a speedup of 18-20 on 36 cores on both real and synthetic datasets of up to 250,000 points. Source code for SHRINK is available for download on our website, http://cucis.ece.northwestern.edu.

AB - Hierarchical clustering has many advantages over traditional clustering algorithms like k-means, but it suffers from higher computational costs and a less obvious parallel structure. Thus, in order to scale this technique up to larger datasets, we present SHRINK, a novel shared-memory algorithm for single-linkage hierarchical clustering based on merging the solutions from overlapping sub-problems. In our experiments, we find that SHRINK provides a speedup of 18-20 on 36 cores on both real and synthetic datasets of up to 250,000 points. Source code for SHRINK is available for download on our website, http://cucis.ece.northwestern.edu.

UR - http://www.scopus.com/inward/record.url?scp=84880287493&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880287493&partnerID=8YFLogxK

U2 - 10.1109/HiPC.2012.6507511

DO - 10.1109/HiPC.2012.6507511

M3 - Conference contribution

AN - SCOPUS:84880287493

SN - 9781467323703

T3 - 2012 19th International Conference on High Performance Computing, HiPC 2012

BT - 2012 19th International Conference on High Performance Computing, HiPC 2012

T2 - 2012 19th International Conference on High Performance Computing, HiPC 2012

Y2 - 18 December 2012 through 21 December 2012

ER -

Parallel hierarchical clustering on shared memory platforms

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this