Fast Clustering using MapReduce

Details Fast Clustering using MapReduce Fast Clustering using MapReduce

2011-09-07

arxiv.org/abs/1109.1579v1

Computer Science

Distributed, Parallel, and Cluster Computing

Accepted to KDD 2011

Scientific paper

Clustering problems have numerous applications and are becoming more challenging as the size of the data increases. In this paper, we consider designing clustering algorithms that can be used in MapReduce, the most popular programming environment for processing large datasets. We focus on the practical and popular clustering problems, $k$-center and $k$-median. We develop fast clustering algorithms with constant factor approximation guarantees. From a theoretical perspective, we give the first analysis that shows several clustering algorithms are in $\mathcal{MRC}^0$, a theoretical MapReduce class introduced by Karloff et al. \cite{KarloffSV10}. Our algorithms use sampling to decrease the data size and they run a time consuming clustering algorithm such as local search or Lloyd's algorithm on the resulting data set. Our algorithms have sufficient flexibility to be used in practice since they run in a constant number of MapReduce rounds. We complement these results by performing experiments using our algorithms. We compare the empirical performance of our algorithms to several sequential and parallel algorithms for the $k$-median problem. The experiments show that our algorithms' solutions are similar to or better than the other algorithms' solutions. Furthermore, on data sets that are sufficiently large, our algorithms are faster than the other parallel algorithms that we tested.

Affiliated with

Also associated with

No associations

Rating

Fast Clustering using MapReduce does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Clustering using MapReduce, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Clustering using MapReduce will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-474183