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

Yewang Chen, Lida Zhou, Songwen Pei, Zhiwen Yu, Yi Chen, Xin Liu, Ji‐Xiang Du, Naixue XiongIEEE Transactions on Systems Man and Cybernetics Systems 2019 · DOI

Abstract

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 ρ-approximate DBSCAN and AnyDBC.
BibTeX
@article{chen2019knn,
  author = {Yewang Chen and Lida Zhou and Songwen Pei and Zhiwen Yu and Yi Chen and Xin Liu and Ji‐Xiang Du and Naixue Xiong},
  title = {{KNN-BLOCK DBSCAN: Fast Clustering for Large-Scale Data}},
  journal = {IEEE Transactions on Systems Man and Cybernetics Systems},
  year = {2019},
  doi = {10.1109/tsmc.2019.2956527},
}

Loading related content...

Figure