A fast DBSCAN algorithm for big data based on efficient density calculation. (1st October 2022)

• Record Type: Journal Article
• Authors: Hanafi, Nooshin; Saadatfar, Hamid
• Is Part Of: Expert systems with applications. Volume 203(2022)
• Publication Date: 2022-10-01
• Subjects: Data Mining -- Clustering -- Big Data -- DBSCAN Algorithm; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2022.117501
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Proposing a fast and accurate version of DBSCAN algorithm for big data. Calculating density based on a small subset of data called operational set. Creating and updating the operational set at a very low computational cost. Comprehensive evaluation of the proposed method in compared to other recent works. Abstract: Today, data is being generated with a high speed. Managing large volume of data has become a challenge in the current age. Clustering is a method to analyze data that is generated in the Internet. Various approaches have been presented for data clustering until now. Among them, DBSCAN is a most well-known density-based clustering algorithm. This algorithm can detect clusters of different shapes and does not require prior knowledge about the number of clusters. A major part of the DBSCAN run-time is spent to calculate the distance of data from each other to find the neighbors of each sample in the dataset. The time complexity of this algorithm is O(n 2 ); Therefore, it is not suitable for processing big datasets. In this paper, DBSCAN is improved so that it can be applied to big datasets. The proposed method calculates accurately each sample density based on a reduced set of data. This reduced set is called the operational set. This collection is updated periodically. The use of local samples to calculate the density has greatly reduced the computational cost of clustering. The empirical results on various datasets of different sizes and dimensions show that the proposed algorithm increases the clustering speed compared to recent related works while having similar accuracy as the original DBSCAN algorithm.