A fast DBSCAN algorithm using a bi-directional HNSW index structure for big data

The Density Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm is one of the most popular and effective density-based clustering algorithms at present. Although it can effectively identify clusters and noise points of arbitrary shapes, it is very difficult to efficiently address the tasks with large scale data. The time complexity of the DBSCAN is \(O(n^2)\) where its main computation time lies in \(\varepsilon\)-neighbor range query, which becomes the bottleneck of DBSCAN performance. To solve this problem, we propose a simple fast DBSCAN algorithm, called bh-DBSCAN, using a bi-directional HNSW index structure to improve the efficiency of DBSCAN by reducing redundant \(\varepsilon\)-neighbor range queries. Specifically, we first distinguish a point’s property (core point or border point). Next, we apply the filtNoise algorithm to filter the noise points that without core points in \(neighbor_x\). Finally, we utilized the MergeCore algorithm to merge the cluster of border points in it’s core neighbor points. The experimental results show that our proposed algorithm could greatly improve the clustering efficiency without losing much accuracy based on the datasets tested.