Timezone: »

 
Poster
Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #1106
in Poster Session 1 »
We consider $k$-means clustering of $n$ data points in Euclidean space in the Massively Parallel Computation (MPC) model, a computational model which is an abstraction of modern massively parallel computing system such as MapReduce. Recent work provides evidence that getting $O(1)$-approximate $k$-means solution for general input points using $o(\log n)$ rounds in the MPC model may be impossible under certain conditions [Ghaffari, Kuhn \& Uitto'2019]. However, the real-world data points usually have better structures. One instance of interest is the set of data points which is perturbation resilient [Bilu \& Linial'2010]. In particular, a point set is $\alpha$-perturbation resilient for $k$-means if perturbing pairwise distances by multiplicative factors in the range $[1,\alpha]$ does not change the optimum $k$-means clusters. We bypass the worst case lower bound by considering the perturbation resilient input points and showing $o(\log n)$ rounds $k$-means clustering algorithms for these instances in the MPC model. Specifically, we show a fully scalable $(1+\varepsilon)$-approximate $k$-means clustering algorithm for $O(\alpha)$-perturbation resilient instance in the MPC model using $O(1)$ rounds and ${O}_{\varepsilon,d}(n^{1+1/\alpha^2+o(1)})$ total space. If the space per machine is sufficiently larger than $k$, i.e., at least $k\cdot n^{\Omega(1)}$, we also develop an optimal $k$-means clustering algorithm for $O(\alpha)$-perturbation resilient instance in MPC using $O(1)$ rounds and ${O}_d(n^{1+o(1)}\cdot(n^{1/\alpha^2}+k))$ total space.
Keywords: OPT: Large Scale, Parallel and Distributed · Theory · MISC: Scalable Algorithms · MISC: Unsupervised and Semi-supervised Learning
[ Slides]  [ Poster]  [ Paper PDF] 

Author Information

Vincent Cohen-Addad (Google)
Vahab Mirrokni (Google Research)
Peilin Zhong (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors