Efficient Map/Reduce-Based DBSCAN Algorithm with Optimized Data Partition

DBSCAN is a well-known algorithm for density-based clustering because it can identify the groups of arbitrary shapes and deal with noisy datasets. However, with the increasing amount of data, DBSCAN algorithm running on a single machine has to face the scalability problem. In this paper, we propose a Map/Reduce-based DBSCAN algorithm called DBSCAN-MR to solve the scalability problem. In DBSCAN-MR, the input dataset is partitioned into smaller parts and then parallel processed on the Hadoop platform. However, choosing different partition mechanisms will affect the execution efficiency and load balance of each node. Therefore, we propose a method, partition with reduce boundary points (PRBP), to select partition boundaries based on the distribution of data points. Our experimental results show that DBSCAN-MR with the design of PRBP has higher efficiency and scalability than competitors.