Efficient hierarchical clustering for singledimensional data using CUDA
Abstract
Hierarchical clustering is a widely-used clustering technique. The classical hierarchical clustering algorithm is prohibitively expensive for large datasets. Existing research has proposed efficiency improvements through parallelism. Recent approaches utilise GPGPU technologies, facilitating massive parallelism on commodity hardware. Existing GPGPU implementations fail to maximise the number of merges performed in parallel, and feature high memory use. These limitations preclude achieving the full performance offered by GPGPU. In this paper, we propose a novel GPGPU algorithm for hierarchical clustering of single-dimensional data. Our proposed algorithm exploits the unique characteristics of one-dimensional data to maximise merge parallelism and significantly reduce memory requirements. Validation demonstrates that our proposed algorithm produces equivalent results to the classical algorithm for both the single-linkage and complete-linkage metrics. Benchmarking results show the algorithm scales well to large datasets, and offers a substantial speed-up over the classical algorithm. Future work will extend our proposed approach to data with higher dimensions.