An Experimental Comparison of GPU Techniques for DBSCAN Clustering

Hamza Mustafa, Eleazar Leal, Le Gruenwald

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

DBSCAN is a density-based clustering algorithm that is especially useful for finding clusters of arbitrary shapes. As opposed to other clustering techniques, like K-means, it does not require the number of clusters to be specified as an input parameter, and it is highly robust to outliers. However, DBSCAN has a worst-case quadratic time complexity, which makes it difficult to handle large dataset sizes. To address this problem, several works have been proposed that exploit the massive parallelism of GPUs in DBSCAN clustering. Nonetheless, none of these works have been experimentally compared against each other. In this paper, we review the existing GPU algorithms for DBSCAN clustering and conduct the first experimental study comparing these GPU algorithms using three real-world datasets to identify the best performing algorithm. Our results show that CUDA-DClust is the best performing GPU algorithm in terms of execution time and memory requirements.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE International Conference on Big Data, Big Data 2019
EditorsChaitanya Baru, Jun Huan, Latifur Khan, Xiaohua Tony Hu, Ronay Ak, Yuanyuan Tian, Roger Barga, Carlo Zaniolo, Kisung Lee, Yanfang Fanny Ye
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3701-3710
Number of pages10
ISBN (Electronic)9781728108582
DOIs
StatePublished - Dec 2019
Event2019 IEEE International Conference on Big Data, Big Data 2019 - Los Angeles, United States
Duration: Dec 9 2019Dec 12 2019

Publication series

NameProceedings - 2019 IEEE International Conference on Big Data, Big Data 2019

Conference

Conference2019 IEEE International Conference on Big Data, Big Data 2019
CountryUnited States
CityLos Angeles
Period12/9/1912/12/19

    Fingerprint

Keywords

  • DBSCAN
  • GPU
  • clustering
  • parallel computing

Cite this

Mustafa, H., Leal, E., & Gruenwald, L. (2019). An Experimental Comparison of GPU Techniques for DBSCAN Clustering. In C. Baru, J. Huan, L. Khan, X. T. Hu, R. Ak, Y. Tian, R. Barga, C. Zaniolo, K. Lee, & Y. F. Ye (Eds.), Proceedings - 2019 IEEE International Conference on Big Data, Big Data 2019 (pp. 3701-3710). [9006169] (Proceedings - 2019 IEEE International Conference on Big Data, Big Data 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData47090.2019.9006169