# Distributed k-Means with Outliers in General Metrics

arXiv: https://arxiv.org/abs/2202.08173 · HTML: https://mlsanity.com/paper/2202.08173/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 16 Feb 2022.

## Builds on (most cited first, 11 of 11)

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [Communication Steps for Parallel Query Processing](https://mlsanity.com/paper/1306.5972/) (2013)
- [Approximation Schemes for Clustering with Outliers](https://mlsanity.com/paper/1707.04295/) (2017)
- [A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++](https://mlsanity.com/paper/1605.04986/) (2016)
- [Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially](https://mlsanity.com/paper/1802.09205/) (2018)
- [A Practical Algorithm for Distributed Clustering and Outlier Detection](https://mlsanity.com/paper/1805.09495/) (2018)
- [Distributed k-Clustering for Data with Heavy Noise](https://mlsanity.com/paper/1810.07852/) (2018)
- [Distributed Partial Clustering](https://mlsanity.com/paper/1703.01539/) (2017)
- [Accurate MapReduce Algorithms for k-median and k-means in General Metric Spaces](https://mlsanity.com/paper/1904.12728/) (2019)

## Abstract (arXiv)

Center-based clustering is a pivotal primitive for unsupervised learning and data analysis. A popular variant is undoubtedly the k-means problem, which, given a set P of points from a metric space and a parameter k<|P|, requires to determine a subset S of k centers minimizing the sum of all squared distances of points in P from their closest center. A more general formulation, known as k-means with z outliers, introduced to deal with noisy datasets, features a further parameter z and allows up to z points of P (outliers) to be disregarded when computing the aforementioned sum. We present a distributed coreset-based 3-round approximation algorithm for k-means with z outliers for general metric spaces, using MapReduce as a computational model. Our distributed algorithm requires sublinear local memory per reducer, and yields a solution whose approximation ratio is an additive term O(γ) away from the one achievable by the best known sequential (possibly bicriteria) algorithm, where γ can be made arbitrarily small. An important feature of our algorithm is that it obliviously adapts to the intrinsic complexity of the dataset, captured by the doubling dimension D of the metric space. To the best of our knowledge, no previous distributed approaches were able to attain similar quality-performance tradeoffs for general metrics.