Title: K-DBSCAN: an efficient density-based clustering algorithm supports parallel computing

Authors: Chao Deng; Jinwei Song; Saihua Cai; Ruizhi Sun; Yinxue Shi; Shangbo Hao

Addresses: College of Information and Electrical Engineering, China Agricultural University, Beijing, 100083, China; China Tobacco Guangxi Industrial Co., Ltd., No. 28 Beihunanlu, Xixiangtang District, Nanning, 530001, China ' National Space Science Center of CAS, No. 1 Nanertiao, Zhongguancun, Haidian district, Beijing, 100190, China ' College of Information and Electrical Engineering, China Agricultural University, Beijing, 100083, China ' College of Information and Electrical Engineering, China Agricultural University, Beijing, 100083, China ' College of Information and Electrical Engineering, China Agricultural University, Beijing, 100083, China ' College of Information and Electrical Engineering, China Agricultural University, Beijing, 100083, China

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²/KC), where K is the number of data partitions, and C is the number of physical computing cores.

Keywords: DBSCAN; data mining; parallel computing; k-means; density-based; clustering; spatial data.

DOI: 10.1504/IJSPM.2018.094740

International Journal of Simulation and Process Modelling, 2018 Vol.13 No.5, pp.496 - 505

Received: 29 Sep 2017
Accepted: 08 May 2018
Published online: 14 Sep 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article