BLOCK-DBSCAN: Fast clustering for large scale data

We analyze the drawbacks of DBSCAN and its variants, and find the grid technique, which is used in Fast-DBSCAN and rho-approximate DBSCAN, is almost useless in high dimensional data space. Because it usually yields considerable redundant distance computations. In order to tame these problems, two techniques are proposed: one is to use xi-norm ball to identify Inner Core Blocks within which all points are core points, it has higher efficiency than grid technique for finding more core points at one time; the other is a fast approximate algorithm for judging whether two Inner Core Blocks are density-reachable from each other. Besides, cover tree is also used to accelerate the process of density computations. Based on the three techniques, an approximate approach, namely BLOCK-DBSCAN, is proposed for large scale data, which runs in about O(nlog (n)) expected time and obtains almost the same result as DBSCAN. BLOCK-DBSCAN has two versions, i.e., L-2 version can work well for relatively high dimensional data, and L-infinity version is suitable for high dimensional data. Experimental results show that BLOCK-DBSCAN is promising and outperforms NQDBSCAN, rho-approximate DBSCAN and AnyDBC. (C) 2020 Elsevier Ltd. All rights reserved.

Automated summary

The article analyzes the drawbacks of DBSCAN and its variants, proposing two techniques for improvement: xi-norm ball and fast approximate algorithm. Additionally, cover tree is used to accelerate density computations, and a method called BLOCK-DBSCAN is introduced for large-scale data.