# Differentially Private k-Means Clustering

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2015.

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

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Differentially Private Synthetic Data via Foundation Model APIs 1: Images](https://mlsanity.com/paper/2305.15560/) (2023)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Differentially Private Vertical Federated Clustering](https://mlsanity.com/paper/2208.01700/) (2022)
- [From Easy to Hard: Building a Shortcut for Differentially Private Image Synthesis](https://mlsanity.com/paper/2504.01395/) (2025)
- [The Importance of Being Discrete: Measuring the Impact of Discretization in End-to-End Differentially Private Synthetic Data](https://mlsanity.com/paper/2504.06923/) (2025)
- [Clustering and Median Aggregation Improve Differentially Private Inference](https://mlsanity.com/paper/2506.04566/) (2025)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Differentially-Private Sublinear-Time Clustering](https://mlsanity.com/paper/2112.13751/) (2021)
- [k-Means SubClustering: A Differentially Private Algorithm with Improved Clustering Quality](https://mlsanity.com/paper/2301.02896/) (2023)
- [FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy](https://mlsanity.com/paper/2405.02437/) (2024)
- [Achieving differential privacy for k-nearest neighbors based outlier detection by data partitioning](https://mlsanity.com/paper/2104.07938/) (2021)
- [Differentially Private Algorithms for Clustering with Stability Assumptions](https://mlsanity.com/paper/2106.12959/) (2021)
- [DPM: Clustering Sensitive Data through Separation](https://mlsanity.com/paper/2307.02969/) (2023)
- [Differentially Private Preference Data Synthesis for Large Language Model Alignment](https://mlsanity.com/paper/2605.30808/) (2026)
- [I still know it's you! On Challenges in Anonymizing Source Code](https://mlsanity.com/paper/2208.12553/) (2022)
- [Improving the Utility of Differentially Private Clustering through Dynamical Processing](https://mlsanity.com/paper/2304.13886/) (2023)
- [Personalized Privacy Amplification via Importance Sampling](https://mlsanity.com/paper/2307.10187/) (2023)
- [Aggregating Data for Optimal and Private Learning](https://mlsanity.com/paper/2411.19045/) (2024)
- [Private Linear Regression with Differential Privacy and PAC Privacy](https://mlsanity.com/paper/2412.02578/) (2024)
- [Privacy-Preserving Vertical K-Means Clustering](https://mlsanity.com/paper/2504.07578/) (2025)
- [Understanding the Impact of Data Domain Extraction on Synthetic Data Privacy](https://mlsanity.com/paper/2504.08254/) (2025)
- [Private Training & Data Generation by Clustering Embeddings](https://mlsanity.com/paper/2506.16661/) (2025)
- [Minimax optimal differentially private synthetic data for smooth queries](https://mlsanity.com/paper/2602.01607/) (2026)
- [PE-means: Improved Differentially Private k-means Clustering through Private Evolution](https://mlsanity.com/paper/2606.00342/) (2026)
- [Geometry-Adaptive Mechanisms for Private Synthetic Data](https://mlsanity.com/paper/2609.33363/) (2026)

## Abstract (arXiv)

There are two broad approaches for differentially private data analysis. The interactive approach aims at developing customized differentially private algorithms for various data mining tasks. The non-interactive approach aims at developing differentially private algorithms that can output a synopsis of the input dataset, which can then be used to support various data mining tasks. In this paper we study the tradeoff of interactive vs. non-interactive approaches and propose a hybrid approach that combines interactive and non-interactive, using k-means clustering as an example. In the hybrid approach to differentially private k-means clustering, one first uses a non-interactive mechanism to publish a synopsis of the input dataset, then applies the standard k-means clustering algorithm to learn k cluster centroids, and finally uses an interactive approach to further improve these cluster centroids. We analyze the error behavior of both non-interactive and interactive approaches and use such analysis to decide how to allocate privacy budget between the non-interactive step and the interactive step. Results from extensive experiments support our analysis and demonstrate the effectiveness of our approach.