# Distributed k-Clustering for Data with Heavy Noise

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2018.

## Built on by (most cited first, 6 of 6)

- [Fast Distributed k-Means with a Small Number of Rounds](https://mlsanity.com/paper/2201.13217/) (2022)
- [Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers](https://mlsanity.com/paper/2301.02814/) (2023)
- [Optimal Transport Aggregation for Distributed Mixture-of-Experts](https://mlsanity.com/paper/2312.09877/) (2023)
- [Distributed k-Means with Outliers in General Metrics](https://mlsanity.com/paper/2202.08173/) (2022)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [Distributed Clustering based on Distributional Kernel](https://mlsanity.com/paper/2409.09418/) (2024)

## Abstract (arXiv)

In this paper, we consider the k-center/median/means clustering with outliers problems (or the (k, z)-center/median/means problems) in the distributed setting. Most previous distributed algorithms have their communication costs linearly depending on z, the number of outliers. Recently Guha et al. overcame this dependence issue by considering bi-criteria approximation algorithms that output solutions with 2z outliers. For the case where z is large, the extra z outliers discarded by the algorithms might be too large, considering that the data gathering process might be costly. In this paper, we improve the number of outliers to the best possible (1+ε)z, while maintaining the O(1)-approximation ratio and independence of communication cost on z. The problems we consider include the (k, z)-center problem, and (k, z)-median/means problems in Euclidean metrics. Implementation of the our algorithm for (k, z)-center shows that it outperforms many previous algorithms, both in terms of the communication cost and quality of the output solution.