cuSLINK: Single-Linkage Agglomerative Clustering on the GPU

Nolet, Corey J.; Gala, Divye; Fender, Alexandre; Doijade, Mahesh; Eaton, Joe; Raff, Edward; Zedlewski, John; Rees, Brad; Oates, Tim

doi:10.1007/978-3-031-43412-9_42

cuSLINK: Single-Linkage Agglomerative Clustering on the GPU

Corey J. Nolet, Divye Gala, Alexandre Fender, Mahesh Doijade, Joe Eaton, Edward Raff, John Zedlewski, Brad Rees, Tim Oates

ECML-PKDD 2023 pp. 711-726

doi:10.1007/978-3-031-43412-9_42 /ecmlpkdd/2023/nolet2023ecmlpkdd-cuslink/

Abstract

In this paper, we propose cuSLINK, a novel and state-of-the-art reformulation of the SLINK algorithm on the GPU which requires only O ( Nk ) space and uses a parameter k to trade off space and time. We also propose a set of novel and reusable building blocks that compose cuSLINK. These building blocks include highly optimized computational patterns for k -NN graph construction, spanning trees, and dendrogram cluster extraction. We show how we used our primitives to implement cuSLINK end-to-end on the GPU, further enabling a wide range of real-world data mining and machine learning applications that were once intractable. In addition to being a primary computational bottleneck in the popular HDBSCAN algorithm, the impact of our end-to-end cuSLINK algorithm spans a large range of important applications, including cluster analysis in social and computer networks, natural language processing, and computer vision.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Nolet et al. "cuSLINK: Single-Linkage Agglomerative Clustering on the GPU." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023. doi:10.1007/978-3-031-43412-9_42

Markdown

[Nolet et al. "cuSLINK: Single-Linkage Agglomerative Clustering on the GPU." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023.](https://mlanthology.org/ecmlpkdd/2023/nolet2023ecmlpkdd-cuslink/) doi:10.1007/978-3-031-43412-9_42

BibTeX

@inproceedings{nolet2023ecmlpkdd-cuslink,
  title     = {{cuSLINK: Single-Linkage Agglomerative Clustering on the GPU}},
  author    = {Nolet, Corey J. and Gala, Divye and Fender, Alexandre and Doijade, Mahesh and Eaton, Joe and Raff, Edward and Zedlewski, John and Rees, Brad and Oates, Tim},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2023},
  pages     = {711-726},
  doi       = {10.1007/978-3-031-43412-9_42},
  url       = {https://mlanthology.org/ecmlpkdd/2023/nolet2023ecmlpkdd-cuslink/}
}