A parallel DBSCAN algorithm based on KD-tree partitioning and a merging strategy
Hongbin Zeng, Xuezhong Qian, Wei Song · 2023
DBSCAN algorithm is a representative density-based clustering algorithm that has gained widespread application due to its ability to discover cluster of arbitrarily shapes and effectively handle noisy data. However, as the size of data increases, the performance of the classical single-machine sequential DBSCAN algorithm deteriorates significantly, failing to meet the efficiency requirements of real-world big data environments. To address this issue, this paper proposes a distributed parallel clustering algorithm – pDBSCAN. pDBSCAN uses Spark, a big data computing framework, to parallelize the algorithm. Furthermore, pDBSCAN leverages K-D Tree neighborhood queries to reduce distance calculations between points, and it divides the dataset into multiple balanced data partitions, thereby enhancing the algorithm’s parallel performance. Additionally, to improve clustering effectiveness, an improved cluster merging strategy based on natural domain similarity is proposed for partial cluster merging. The performance and effectiveness of the pDBSCAN algorithm are evaluated in this paper based on real datasets, fully demonstrating the effectiveness and superiority of the proposed algorithm.