A new scalable parallel DBSCAN algorithm using the disjoint-set data structure

Citations Over TimeTop 10% of 2012 papers

Abstract

DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of DBSCAN is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel DBSCAN algorithm (PDSDBSCAN) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of DBSCAN. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for shared and for distributed memory. Using data sets containing up to several hundred million high-dimensional points, we show that PDSDBSCAN significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on shared memory architecture, and speedups up to 5,765 using 8,192 cores on distributed memory architecture.

Related Papers

• → Software based distributed shared memory (DSM) model using shared variables between multiprocessors(2015)6 cited
• → Distributed shared memory(1992)3 cited
• → Distributed shared memory(1992)2 cited
• → Experiences in integrating distributed shared memory with virtual memory management(1992)10 cited
• Principle and Implementing Method fot MPP System of Distributed Shared Memory(1993)