# PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 53 references that are in the map.
- First posted on arXiv 11 Jan 2024.

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

- [Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm](https://mlsanity.com/paper/2209.05757/) (2022)
- [Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering](https://mlsanity.com/paper/2104.01126/) (2021)
- [A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs](https://mlsanity.com/paper/2207.00514/) (2022)
- [ArborX: A Performance Portable Geometric Search Library](https://mlsanity.com/paper/1908.11807/) (2019)
- [Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees](https://mlsanity.com/paper/2103.15217/) (2021)

## Abstract (arXiv)

This paper presents pandora, a novel parallel algorithm for efficiently constructing dendrograms for single-linkage hierarchical clustering, including hdbscan. Traditional dendrogram construction methods from a minimum spanning tree (MST), such as agglomerative or divisive techniques, often fail to efficiently parallelize, especially with skewed dendrograms common in real-world data. pandora addresses these challenges through a unique recursive tree contraction method, which simplifies the tree for initial dendrogram construction and then progressively reconstructs the complete dendrogram. This process makes pandora asymptotically work-optimal, independent of dendrogram skewness. All steps in pandora are fully parallel and suitable for massively threaded accelerators such as GPUs. Our implementation is written in Kokkos, providing support for both CPUs and multi-vendor GPUs (e.g., Nvidia, AMD). The multithreaded version of pandora is 2.2× faster than the current best-multithreaded implementation, while the GPU pandora implementation achieved 6-20× on amdgpu and 10-37× on nvidiagpu speed-up over multithreaded pandora. These advancements lead to up to a 6-fold speedup for hdbscan on GPUs over the current best, which only offload MST construction to GPUs and perform multithreaded dendrogram construction.