CUDA-DClust+: revisiting early GPU-accelerated DBSCAN clustering designs

Poudel, Madhav (2021) CUDA-DClust+: revisiting early GPU-accelerated DBSCAN clustering designs. Masters thesis, Northern Arizona University.

Text Poudel_2021_cuda-dclust+_revisiting_early_gpu-accelerated_dbscan_clust.pdf - Published Version Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Density-based clustering algorithms are widely used unsupervised data mining techniques to find the clusters of points in dense regions that are separated by low-density regions. This algorithm is inherently sequential and has limitations in its parallel implementation. There have been several parallel algorithms presented in the literature for multi-core CPUs and many-core GPUs. One such algorithm for the GPU is CUDA-DClust. In this paper, we propose a new GPU-accelerated DBSCAN algorithm with several optimizations. In comparison to prior work, our algorithm, CUDA-DClust+: (i) computes the indexing structure on the GPU, (ii) uses kernel fusion to combine the index search and cluster expansion kernels, which reduces communication and synchronization overhead with the host, and (iii) seed list management control is primarily given to the GPU rather than the CPU, which further decreases CPU-GPU communication overhead. We compare our algorithm to three state-of-the-art parallel algorithms in the literature on six real-world datasets. We find that our algorithm achieves a speedup of up to ~23x over the fastest GPU algorithm.

Item Type:	Thesis (Masters)
Publisher’s Statement:	© Copyright is held by the author. Digital access to this material is made possible by the Cline Library, Northern Arizona University. Further transmission, reproduction or presentation of protected items is prohibited except with permission of the author.
Keywords:	Clustering; DBSCAN; GPGPU; Graphics Processing Unit; Machine Learning; Outlier Detection
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
NAU Depositing Author Academic Status:	Student
Department/Unit:	Graduate College > Theses and Dissertations College of Engineering, Informatics, and Applied Sciences > School of Informatics, Computing, and Cyber Systems
Date Deposited:	04 Feb 2022 20:56
Last Modified:	04 Feb 2022 20:56
URI:	https://openknowledge.nau.edu/id/eprint/5652

Actions (login required)

IR Staff Record View

Downloads