PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU
Piyush Sao, Andrey Prokopenko, Damien Lebrun-Grandié · 2024
This paper introduces Pandora, a parallel algorithm for computing dendrograms, the hierarchical cluster trees for single linkage clustering (SLC). Current parallel approaches construct dendrograms by partitioning a minimum spanning tree and removing edges. However, they struggle with skewed, hard-to-parallelize real-world dendrograms. Consequently, computing dendrograms is the sequential bottleneck in HDBSCAN*[21], a popular SLC variant.