KNN-BLOCK DBSCAN: Fast Clustering for Large-Scale Data

Large-scale data clustering is an essential key for big data problem. However, no current existing approach is optimal for big data due to high complexity, which remains it a great challenge. In this article, a simple but fast approximate DBSCAN, namely, KNN-BLOCK DBSCAN, is proposed based on two findings: 1) the problem of identifying whether a point is a core point or not is, in fact, a kNN problem and 2) a point has a similar density distribution to its neighbors, and neighbor points are highly possible to be the same type (core point, border point, or noise). KNN-BLOCK DBSCAN uses a fast approximate kNN algorithm, namely, FLANN, to detect core-blocks (CBs), noncore-blocks, and noise-blocks within which all points have the same type, then a fast algorithm for merging CBs and assigning noncore points to proper clusters is also invented to speedup the clustering process. The experimental results show that KNN-BLOCK DBSCAN is an effective approximate DBSCAN algorithm with high accuracy, and outperforms other current variants of DBSCAN, including rho-approximate DBSCAN and AnyDBC.

Automated summary

This article proposes a fast approximate DBSCAN algorithm, KNN-BLOCK DBSCAN, based on kNN problem, which detects core-blocks, noncore-blocks, and noise-blocks, and merges CBs while assigning noncore points to proper clusters for efficient data clustering.