2011 FastClusteringUsingMapReduce

• (Ene et al., 2011) ⇒ Alina Ene, Sungjin Im, and Benjamin Moseley. (2011). “Fast Clustering Using MapReduce.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020515

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Fast+Clustering+Using+MapReduce
• http://dl.acm.org/citation.cfm?id=2020408.2020515&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; approximation algorithms; clustering algorithms; experimentation; k-center; k-median; mapreduce; nonnumerical algorithms and problems; parallel algorithms; theory

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 FastClusteringUsingMapReduce	Alina Ene Sungjin Im Benjamin Moseley			Fast Clustering Using MapReduce				10.1145/2020408.2020515		2011