Skip to main content
SHARE
Publication

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

by Piyush K Sao, Andrey V Prokopenko, Damien T Lebrun-grandie
Publication Type
Conference Paper
Book Title
ICPP '24: Proceedings of the 53rd International Conference on Parallel Processing
Publication Date
Page Numbers
908 to 918
Publisher Location
New York, New York, United States of America
Conference Name
53rd International Conference on Parallel Processing (ICPP2024)
Conference Location
Visby, Gotland, Sweden
Conference Sponsor
ACM
Conference Date
-

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.

Pandora uses recursive tree contraction to address this limitation. Pandora contracts nodes to construct progressively smaller trees. It computes the smallest contracted dendrogram and expands it by inserting contracted edges. This recursive strategy is highly parallel, skew-independent, work-optimal, and well-suited for GPUs and multicores.

We develop a performance portable implementation of Pandora in Kokkos[31] and evaluate its performance on multicore CPUs and multi-vendor GPUs (e.g., Nvidia, AMD) for dendrogram construction in HDBSCAN*. Multithreaded Pandora is 2.2x faster than the current best-multithreaded implementation. Our GPU version achieves 6-20x speedup on AMD GPUs and 10-37x on NVIDIA GPUs over multithreaded Pandora. Pandora removes HDBSCAN*’s sequential bottleneck, greatly boosting efficiency, particularly with GPUs.