Anytime Algorithm for Cell-based DBSCAN by Connecting Randomly Selected Cells

With the growing interest in big data, speed-up techniques for clustering are required. The density-based spatial clustering of applications with noise (DBSCAN) has been well known in database domains. Since the DBSCAN algorithm was first proposed, several speed-up methods have been introduced. In the previous work, cell-based DBSCAN as a fast DBSCAN algorithm that divides the whole dataset into smaller cells and connects them to form clusters was proposed. In this study we propose a novel clustering algorithm called anytime algorithm for cell-based DBSCAN. The proposed algorithm connects some randomly selected cells and calculates the clustering result at high speed. Next, it repeats this process, which improves the accuracy of clustering, thereby yielding the precise results. Experimental results demonstrated that the proposed algorithm can calculate the clustering results with high accuracy at high speed.