Fast clustering using MapReduce
Authors:
Open Access
- 21 August 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 681-689
Abstract
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 MRC0, a theoretical MapReduce class introduced by Karloff et al. [26]. 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.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- On distributing symmetric streaming computationsACM Transactions on Algorithms, 2010
- Streaming Algorithms for k-Center Clustering with Outliers and with AnonymityLecture Notes in Computer Science, 2008
- Quick k-Median, k-Center, and Facility Location for Sparse GraphsSIAM Journal on Computing, 2005
- Incremental Clustering and Dynamic Information RetrievalSIAM Journal on Computing, 2004
- Local Search Heuristics for k-Median and Facility Location ProblemsSIAM Journal on Computing, 2004
- Clustering data streams: theory and practiceIEEE Transactions on Knowledge and Data Engineering, 2003
- A Constant-Factor Approximation Algorithm for the k-Median ProblemJournal of Computer and System Sciences, 2002
- A Best Possible Heuristic for the k-Center ProblemMathematics of Operations Research, 1985
- A simple heuristic for the p-centre problemOperations Research Letters, 1985
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982