Robert Krauthgamer, Weizmann Institute of Science

Abstract

We design new algorithms for k-clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalable, meaning that the local memory in each machine is an arbitrarily small poly(n) for input size n, which importantly may be substantially smaller than k. Our algorithms are fast, i.e., take O(1) rounds, and achieve O(1)-bicriteria approximation for k-Median and for k-Means, while previous work achieves only polylog(n)-approximation or handles special cases.

Our results rely on a fast MPC algorithm for O(1)-approximation of facility location. A primary technical tool that we develop, and may be of independent interest, is a new MPC primitive for geometric aggregation, namely, computing certain statistics on an approximate neighborhood of every data point, which includes range counting and nearest-neighbor search.

Joint work with Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, and Pavel Vesely.

[Video]