MR-DBSCAN: An Efficient Parallel Density-Based Clustering Algorithm Using MapReduce
Authors:
- Yaobin HeYHYaobin He
- Haoyu TanHTHaoyu Tan
- Wuman LuoWLWuman Luo
- Huajian MaoHMHuajian Mao
- Di MaDMDi Ma
- Shengzhong FengSFShengzhong Feng
- Jianping FanJFJianping Fan
- 1 December 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15219097,p. 473-480
Abstract
Data clustering is an important data mining technology that plays a crucial role in numerous scientific applications. However, it is challenging due to the size of datasets has been growing rapidly to extra-large scale in the real world. Meanwhile, MapReduce is a desirable parallel programming platform that is widely applied in kinds of data process fields. In this paper, we propose an efficient parallel density-based clustering algorithm and implement it by a 4-stages MapReduce paradigm. Furthermore, we adopt a quick partitioning strategy for large scale non-indexed data. We study the metric of merge among bordering partitions and make optimizations on it. At last, we evaluate our work on real large scale datasets using Hadoop platform. Results reveal that the speedup and scale up of our work are very efficient.Keywords
This publication has 9 references indexed in Scilit:
- Scalable Clustering Algorithm for N-Body Simulations in a Shared-Nothing Cluster2010
- Experiments in Parallel Clustering with DBSCAN2001
- A Fast Parallel Clustering Algorithm for Large Spatial DatabasesData Mining and Knowledge Discovery, 1999
- OPTICS1999
- The R*-tree: an efficient and robust access method for points and rectanglesACM SIGMOD Record, 1990
- A Partitioning Strategy for Nonuniform Problems on MultiprocessorsIEEE Transactions on Computers, 1987
- R-treesACM SIGMOD Record, 1984
- The Grid FileACM Transactions on Database Systems, 1984
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975