Source-linked AI summary
Fast Clustering using MapReduce
Alina Ene, Sungjin Im, Benjamin Moseley
TL;DR
Large-scale clustering motivates algorithms that operate within MapReduce, particularly for metric k-center and k-median. The paper combines sampling with clustering on reduced datasets to obtain constant-factor approximations in a constant number of rounds, and experiments report similar or better solutions with substantial speedups for k-median. These results establish the problems’ fit within MRC^0 while relying on explicit metric-distance input assumptions.
Problem
The paper asks how to design metric k-center and k-median clustering algorithms for datasets too large to process on a single machine.
Method
The algorithms use sampling to reduce the data size and then run clustering procedures such as local search or Lloyd’s algorithm on the resulting sample within MapReduce.
Results
The paper gives randomized constant-factor approximation algorithms for k-center and k-median running with high probability in a constant number of MapReduce rounds.
Takeaways & Limitations
The algorithms place k-center and k-median in MRC^0 and achieve similar or better k-median solutions while substantially reducing running time on sufficiently large datasets.
Takeaways & Limitations
The algorithms assume triangle-inequality distances given explicitly as a complete set of pairwise distances, with k bounded by O(n^(1−δ)) for constant δ > 0.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops constant-factor approximation algorithms for metric k-center and k-median that run in a constant number of MapReduce rounds, addressing clustering on datasets too large for one machine. It combines sampling with clustering on the reduced data and reports strong empirical speedups for k-median.
- Motivation: Clustering supports applications including machine learning, data mining, networking, bioinformatics, web analysis, and social-network community detection.Large web and social-network graphs can make sequential processing unusable, motivating distributed frameworks such as MapReduce.
- Problems: The paper studies metric k-center and k-median, which choose k centers and assign every point to its closest center.k-center minimizes the maximum assignment distance, while k-median minimizes the corresponding aggregate objective.
- Assumptions: The algorithms assume metric distances satisfying the triangle inequality and use an explicitly represented distance function, with k at most O(n^(1−δ)) for constant δ > 0.The explicit representation consists of Θ(n^2) pairwise distances, or equivalently a weighted complete graph.
- Contributions: The paper introduces approximate k-center and k-median algorithms designed to run in a constant number of MapReduce rounds.The algorithms use sublinear machine memory and establish that both problems belong to the theoretical class MRC^0.
- Theoretical results: For k-center, a randomized constant-approximation algorithm runs with high probability in O(1) MapReduce rounds and uses O(k^2 n^δ) memory per machine.The guarantee holds for any constant δ > 0.
- Theoretical results: For k-median, a randomized constant-approximation algorithm has the same high-probability round and per-machine-memory bounds.It runs in O(1) MapReduce rounds and uses at most O(k^2 n^δ) memory on each machine for any constant δ > 0.
- Experiments: On randomly generated k-median data, the algorithms achieved 1000x speed-up over local search and 20x over parallelized Lloyd’s algorithm.Their objective was similar to Lloyd’s algorithm and local search, and they were faster than the partitioning-based algorithm for sufficiently many points.
- Method: The approach partitions and samples the input, then applies a costly clustering routine such as local search or Lloyd’s algorithm to the smaller resulting dataset.The framework can also collect and cluster centers produced from separate partitions.
2 Algorithms
The algorithms reduce clustering data through iterative sampling, then solve k-center or weighted k-median on the resulting representation in MapReduce. They achieve constant-round, high-probability guarantees while controlling per-machine memory.
- Iterative sampling: The sample size and running time trade off through the parameter ǫ, while each iteration reduces the remaining points by a factor of Θ(n^ǫ) with high probability.The number of iterations is at most O(1/(ǫkn^ǫ log n)) with high probability.
- Iterative sampling: Iterative-Sample repeatedly augments a sample S and removes points from R that are sufficiently represented by the current sample.Sampling continues until the remaining set falls below the algorithm’s threshold.
- MapReduce implementation: MapReduce-Iterative-Sample requires O(1/ǫ) rounds with machine memory O(kn^δ) for any constant δ > 2ǫ, with high probability.The memory analysis depends on storing distances between partitioned remaining points and the sample.
- MapReduce-kCenter: MapReduce-kCenter samples points, gathers pairwise distances within the sample, and runs a k-center algorithm on that reduced instance.The reducer returns the centers constructed from the sampled set C.
- MapReduce-kMedian: MapReduce-kMedian assigns unsampled points to their closest sampled points, aggregates those assignment counts as weights, and runs weighted k-median on the sample.Additional rounds compute the weights, while the machine-memory bound is similar to MapReduce-kCenter.
3 Analysis
The analysis shows that Iterative-Sample produces representative centers with high-probability guarantees, enabling constant-factor approximations for both k-center and k-median. The resulting bounds depend on the approximation algorithm applied to the sampled instance.
- Iterative-Sample analysis: Iterative-Sample uses satisfied and unsatisfied points to analyze how well its returned sample represents the data.A point is satisfied when its sampled center is no farther than its optimal center; the analysis bounds the remaining unsatisfied points.
- Iterative-Sample analysis: With high probability, unsatisfied points admit an injective proxy mapping whose optimal-service distance dominates their distance to the returned centers.This mapping is the core analytical device for bounding the contribution of unsatisfied points.
- k-center: 2OPT is the high-probability upper bound on every point’s distance to the centers returned by Iterative-Sample for k-center.The proof uses the triangle inequality together with the proxy mapping.
- k-center: (4α + 2)-approximation is achieved by MapReduce-kCenter when the final k-center algorithm provides an α-approximation.This combines the sampled-center guarantee with the approximation quality of the algorithm run on the sample.
- k-median: (10α + 3)-approximation is achieved by MapReduce-kMedian when the weighted k-median algorithm provides an α-approximation.The weighted sample uses each sampled point’s number of assigned unsampled points as its weight, and the analysis bounds the weighted optimum by 2OPT(V, C).
4 Experiments
The experiments evaluate sampling- and partitioning-based k-median algorithms against sequential and parallel baselines. Sampling achieves large speedups with small performance loss, while the k-center objective is sensitive to sampling.
- Results: The experiments focus on k-median because the proposed algorithm gives its largest performance increase, while sampling performs poorly for k-center.The k-center objective is sensitive to sampling because it depends on the maximum point-to-center distance.
- Implemented Algorithms: Sampling-LocalSearch and Sampling-Lloyd use Iterative-Sample before applying local search or Lloyd’s algorithm to the resulting sample.Their only difference is the clustering algorithm selected as A in MapReduce-kMedian.
- Implemented Algorithms: MapReduce-Divide-kMedian partitions points, computes centers in parallel, combines them, and clusters the combined center set.It runs in O(1) MapReduce rounds; with an α-approximation subroutine, it achieves a 3α-approximation.
- Implemented Algorithms: Divide-LocalSearch is a constant factor approximation, whereas Lloyd’s algorithm does not provide an approximation guarantee.The parallelized Lloyd implementation used in the experiments works only for points in Euclidean space.
- Results: Sampling-LocalSearch and Sampling-Lloyd achieve about 20x speedup over Parallel-Lloyd and over 1000x speedup over LocalSearch.They also outperform Divide-LocalSearch by more than ten times in the reported experiments.
- Results: The sampling algorithms retain objective performance close to Parallel-Lloyd and LocalSearch despite their speedups.The reported speedup is described as increasing rapidly with the number of points and involving a small performance loss.
- Results: Sampling-Lloyd achieves about 25% speedup over Divide-Lloyd on data sets with 10^7 points.At 5 × 10^6 points, Sampling-LocalSearch is slightly slower than Divide-Lloyd, with similar clustering cost.
5 Conclusion
The paper presents the first approximation algorithms for k-center and k-median that run in a constant number of MapReduce rounds. It also reports preliminary evidence that the k-median analysis may extend to Euclidean k-means.
- The paper gives the first approximation algorithms for k-center and k-median that run in a constant number of MapReduce rounds.
- Preliminary evidence suggests that the k-median analysis can extend to Euclidean k-means with a constant-round, constant-factor approximation.