# DPM: Clustering Sensitive Data through Separation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 6 Jul 2023.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Diffprivlib: The IBM Differential Privacy Library](https://mlsanity.com/paper/1907.02444/) (2019)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions](https://mlsanity.com/paper/1601.03229/) (2016)
- [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Differentially Private Confidence Intervals](https://mlsanity.com/paper/2001.02285/) (2020)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Locally Private k-Means Clustering](https://mlsanity.com/paper/1907.02513/) (2019)
- [Differentially Private Clustering via Maximum Coverage](https://mlsanity.com/paper/2008.12388/) (2020)
- [Federated Boosted Decision Trees with Differential Privacy](https://mlsanity.com/paper/2210.02910/) (2022)
- [Utility-efficient Differentially Private K-means Clustering based on Cluster Merging](https://mlsanity.com/paper/2010.01234/) (2020)

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

- [Public Data Assisted Differentially Private In-Context Learning](https://mlsanity.com/paper/2509.10932/) (2025)

## Abstract (arXiv)

Clustering is an important tool for data exploration where the goal is to subdivide a data set into disjoint clusters that fit well into the underlying data structure. When dealing with sensitive data, privacy-preserving algorithms aim to approximate the non-private baseline while minimising the leakage of sensitive information. State-of-the-art privacy-preserving clustering algorithms tend to output clusters that are good in terms of the standard metrics, inertia, silhouette score, and clustering accuracy, however, the clustering result strongly deviates from the non-private KMeans baseline. In this work, we present a privacy-preserving clustering algorithm called DPM that recursively separates a data set into clusters based on a geometrical clustering approach. In addition, DPM estimates most of the data-dependent hyper-parameters in a privacy-preserving way. We prove that DPM preserves Differential Privacy and analyse the utility guarantees of DPM. Finally, we conduct an extensive empirical evaluation for synthetic and real-life data sets. We show that DPM achieves state-of-the-art utility on the standard clustering metrics and yields a clustering result much closer to that of the popular non-private KMeans algorithm without requiring the number of classes.