# cuSLINK: Single-linkage Agglomerative Clustering on the GPU

arXiv: https://arxiv.org/abs/2306.16354 · HTML: https://mlsanity.com/paper/2306.16354/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 35 references that are in the map.
- First posted on arXiv 28 Jun 2023.

## Builds on (most cited first, 4 of 4)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Accelerated Hierarchical Density Clustering](https://mlsanity.com/paper/1705.07321/) (2017)
- [t-SNE-CUDA: GPU-Accelerated t-SNE and its Applications to Modern Data](https://mlsanity.com/paper/1807.11824/) (2018)
- [Bringing UMAP Closer to the Speed of Light with GPU Acceleration](https://mlsanity.com/paper/2008.00325/) (2020)

## Built on by (most cited first, 2 of 2)

- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Agglomerative Token Clustering](https://mlsanity.com/paper/2409.11923/) (2024)

## Abstract (arXiv)

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 at https://docs.rapids.ai/api/cuml/latest/api/#agglomerative-clustering