Accelerating Density-Based Spatial Clustering of Applications with Noise (DBSCAN) Using Vincenty’s Inverse Method on CUDA

DBSCAN, or Density-Based Spatial Clustering of Applications with Noise, is a well-known density-based clustering algorithm with applications in data mining and machine learning. DBSCAN is designed to detect irregularly shaped clusters as well as noises from a large set of data points by leveraging a distance function. DBSCAN works with any distance function, but the most commonly used is the Euclidean distance. In this study, the DBSCAN algorithm is modified such that the Vincenty’s inverse method is used instead of the Euclidean distance. Vincenty’s inverse method is a more appropriate distance function for calculating geodesic distances in contrast with Euclidean distance which is used for planar distances. However, it is rarely utilized as it is computationally more expensive. To address this issue, this study introduces a novel approach that uses the CUDA compute platform to speed up the implementation of the Vincenty’s inverse method. CUDA, or Compute Unified Device Architecture, is a parallel computing platform built by NVIDIA that allows users to access and control the instruction set and parallel computing components of graphics processing units (GPU). Results showed that the parallel CUDA version of the modified DBSCAN algorithm having a dataset size of 16,384 points took less than 60 s to execute, which is 8.79 times faster than the non-parallel C++ version with a run time of 478.8 s.