MR-DBSCAN: A scalable MapReduce-based DBSCAN algorithm for heavily skewed data

Yaobin He, Haoyu Tan, Wuman Luo, Shengzhong Feng, Jianping Fan

Research output: Contribution to journalArticlepeer-review

145 Citations (Scopus)

Abstract

DBSCAN (density-based spatial clustering of applications with noise) is an important spatial clustering technique that is widely adopted in numerous applications. As the size of datasets is extremely large nowadays, parallel processing of complex data analysis such as DBSCAN becomes indispensable. However, there are three major drawbacks in the existing parallel DBSCAN algorithms. First, they fail to properly balance the load among parallel tasks, especially when data are heavily skewed. Second, the scalability of these algorithms is limited because not all the critical sub-procedures are parallelized. Third, most of them are not primarily designed for shared-nothing environments, which makes them less portable to emerging parallel processing paradigms. In this paper, we present MR-DBSCAN, a scalable DBSCAN algorithm using MapReduce. In our algorithm, all the critical sub-procedures are fully parallelized. As such, there is no performance bottleneck caused by sequential processing. Most importantly, we propose a novel data partitioning method based on computation cost estimation. The objective is to achieve desirable load balancing even in the context of heavily skewed data. Besides, We conduct our evaluation using real large datasets with up to 1.2 billion points. The experiment results well confirm the efficiency and scalability of MR-DBSCAN.

Original languageEnglish
Pages (from-to)83-99
Number of pages17
JournalFrontiers of Computer Science
Volume8
Issue number1
DOIs
Publication statusPublished - Feb 2014
Externally publishedYes

Keywords

  • data clustering
  • data mining
  • load balancing
  • parallel algorithm

Fingerprint

Dive into the research topics of 'MR-DBSCAN: A scalable MapReduce-based DBSCAN algorithm for heavily skewed data'. Together they form a unique fingerprint.

Cite this