# A Practical Algorithm for Distributed Clustering and Outlier Detection

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

## Key facts

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

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

- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Debunking Free Fusion Myth: Online Multi-view Anomaly Detection with Disentangled Product-of-Experts Modeling](https://mlsanity.com/paper/2310.18728/) (2023)
- [Is Simple Uniform Sampling Effective for Center-Based Clustering with Outliers: When and Why?](https://mlsanity.com/paper/2103.00558/) (2021)
- [Learning the Precise Feature for Cluster Assignment](https://mlsanity.com/paper/2106.06159/) (2021)
- [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)
- [Distributed k-Means with Outliers in General Metrics](https://mlsanity.com/paper/2202.08173/) (2022)

## Abstract (arXiv)

We study the classic k-means/median clustering, which are fundamental problems in unsupervised learning, in the setting where data are partitioned across multiple sites, and where we are allowed to discard a small portion of the data by labeling them as outliers. We propose a simple approach based on constructing small summary for the original dataset. The proposed method is time and communication efficient, has good approximation guarantees, and can identify the global outliers effectively. To the best of our knowledge, this is the first practical algorithm with theoretical guarantees for distributed clustering with outliers. Our experiments on both real and synthetic data have demonstrated the clear superiority of our algorithm against all the baseline algorithms in almost all metrics.