Quantum algorithm for MMNG-based DBSCAN

Area of Science:

• Computer Science
• Data Mining
• Quantum Computing

Background:

• Density-based clustering algorithms like DBSCAN are widely used for discovering clusters of arbitrary shapes.
• Classic DBSCAN struggles with datasets exhibiting varying local densities and can be computationally intensive.
• Efficient clustering is crucial for large-scale data analysis and pattern recognition.

Purpose of the Study:

• To address the limitations of classic DBSCAN in handling datasets with diverse local densities.
• To enhance the speed and efficiency of the DBSCAN algorithm.
• To introduce a novel quantum-enhanced approach for density-based clustering.

Main Methods:

• Development of a quantum mutual MinPts-nearest neighbor graph (MMNG) construction.
• Integration of the MMNG into the DBSCAN framework, creating a quantum-enhanced DBSCAN.
• Evaluation of the algorithm's performance on databases with differing local densities.

Main Results:

• The proposed quantum MMNG-based DBSCAN demonstrates superior performance on databases with varying local densities compared to classic DBSCAN.
• A significant increase in clustering speed is observed with the new algorithm.
• The algorithm effectively identifies clusters regardless of density variations.

Conclusions:

• The quantum mutual MinPts-nearest neighbor graph (MMNG)-based DBSCAN is an effective solution for clustering datasets with heterogeneous local densities.
• This quantum-enhanced approach offers substantial speedups, making it suitable for large-scale applications.
• The study highlights the potential of quantum computing principles in improving classical data mining algorithms.