K-DBSCAN: an efficient density-based clustering algorithm supports parallel computing. (2018)

• Record Type: Journal Article
• Authors: Deng, Chao; Song, Jinwei; Cai, Saihua; Sun, Ruizhi; Shi, Yinxue; Hao, Shangbo
• Is Part Of: International journal of simulation and process modelling. Volume 13:Number 5(2018)
• Page Start: 496
• Page End: 505
• Publication Date: 2018
• Subjects: DBSCAN -- data mining -- parallel computing -- k-means -- density-based -- clustering -- spatial data; Management -- Computer simulation -- Periodicals; Mathematical models -- Periodicals; Operations research -- Periodicals; Simulation methods -- Periodicals; 003.05
• Languages: English
• ISSNs: 1740-2123

Abstract

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.