K-DBSCAN: an efficient density-based clustering algorithm supports parallel computing. (2018) - Deng, Chao; Song, Jinwei; Cai, Saihua; Sun, Ruizhi; Shi, Yinxue; Hao, Shangbo
DBSCAN is the most representative density-based clustering algorithm and has been widely used in many fields. However, the running time of DBSCAN is unacceptable in many actual applications. To improve its performance, this paper presents a new 2D density-based clustering algorithm, K-DBSCAN, which successfully reduces the computational complexity of the clustering process by a simplified k-mean partitioning process and a reachable partition index, and enables parallel computing by a divide-and-conquer method. The experiments show that K-DBSCAN achieves remarkable accuracy, efficiency and applicability compared with conventional DBSCAN algorithms especially in large-scale spatial density-based clustering. The time complexity of K-DBSCAN is O ( N 2 / KC ), where K is the number of data partitions, and C is the number of physical computing cores.