cuSLINK: Single-linkage Agglomerative Clustering on the GPU
NVIDIA, Inc, Santa Clara, CA, USA
arXiv:2306.16354 [cs.LG], (28 Jun 2023)
@misc{nolet2023cuslink,
title={cuSLINK: Single-linkage Agglomerative Clustering on the GPU},
author={Corey J. Nolet and Divye Gala and Alex Fender and Mahesh Doijade and Joe Eaton and Edward Raff and John Zedlewski and Brad Rees and Tim Oates},
year={2023},
eprint={2306.16354},
archivePrefix={arXiv},
primaryClass={cs.LG}
}
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. Users can obtain cuSLINK.
July 2, 2023 by hgpu
