BLOCK-DBSCAN: Fast clustering for large scale data. (January 2021)

• Record Type: Journal Article
• Authors: Chen, Yewang; Zhou, Lida; Bouguila, Nizar; Wang, Cheng; Chen, Yi; Du, Jixiang
• Is Part Of: Pattern recognition. Volume 109(2021)
• Publication Date: 2021-01
• Subjects: DBSCAN -- ρ-approximate DBSCAN -- BLOCK-DBSCAN -- Core block; 00-01 -- 99-00; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2020.107624
• Languages: English
• ISSNs: 0031-3203

Abstract

Abstract: We analyze the drawbacks of DBSCAN and its variants, and find the grid technique, which is used in Fast-DBSCAN and ρ -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 ϵ 2 -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 ( n log ( 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 ∞ version is suitable for high dimensional data. Experimental results show that BLOCK-DBSCAN is promising and outperforms NQDBSCAN, ρ -approximate DBSCAN and AnyDBC.