Quantum algorithm for MMNG-based DBSCAN

Xuming Xie; Longzhen Duan; Taorong Qiu; Junru Li

doi:10.1038/s41598-021-95156-7

Quantum algorithm for MMNG-based DBSCAN

Sci Rep. 2021 Jul 30;11(1):15559. doi: 10.1038/s41598-021-95156-7.

Authors

Xuming Xie^#¹, Longzhen Duan^#¹, Taorong Qiu², Junru Li³

Affiliations

¹ School of Information Engineering, Nanchang University, Nanchang, 330031, People's Republic of China.
² School of Information Engineering, Nanchang University, Nanchang, 330031, People's Republic of China. qiutaorong@ncu.edu.cn.
³ School of Software and Internet of Things Engineering, Jiangxi University of Finance and Economics, Nanchang, 330013, People's Republic of China.

^# Contributed equally.

Abstract

DBSCAN is a famous density-based clustering algorithm that can discover clusters with arbitrary shapes without the minimal requirements of domain knowledge to determine the input parameters. However, DBSCAN is not suitable for databases with different local-density clusters and is also a very time-consuming clustering algorithm. In this paper, we present a quantum mutual MinPts-nearest neighbor graph (MMNG)-based DBSCAN algorithm. The proposed algorithm performs better on databases with different local-density clusters. Furthermore, the proposed algorithm has a dramatic increase in speed compared to its classic counterpart.

Abstract

Grants and funding