2018/01/22 by Thapana Boonchoo, Xiang Ao, Boonchoo, Thapana +3
Computer Science · #Advanced Clustering Algorithms Research #Advanced Image and Video Retrieval Techniques #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Information Retrieval (cs.IR)
paper · pdf · doi:10.48550/arxiv.1801.06965
openalex publication_date 2018/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
DBSCAN is a typically used clustering algorithm due to its clustering ability for arbitrarily-shaped clusters and its robustness to outliers. Generally, the complexity of DBSCAN is O(n2) in the worst case, and it practically becomes more severe in higher dimension. Grid-based DBSCAN is one of the recent improved algorithms aiming at facilitating efficiency. However, the performance of grid-based DBSCAN still suffers from two problems: neighbour explosion and redundancies in merging, which make the algorithms infeasible in high-dimensional space. In this paper, we propose a novel algorithm named GDPAM attempting to extend Grid-based DBSCAN to higher data dimension. In GDPAM, a bitmap indexing is utilized to manage non-empty grids so that the neighbour grid queries can be performed efficiently. Furthermore, we adopt an efficient union-find algorithm to maintain the clustering information in order to reduce redundancies in the merging. The experimental results on both real-world and synthetic datasets demonstrate that the proposed algorithm outperforms the state-of-the-art exact/approximate DBSCAN and suggests a good scalability.