# Scalable Differentially Private Clustering via Hierarchically Separated Trees

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 41 references that are in the map.
- First posted on arXiv 17 Jun 2022.

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

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [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)
- [Differentially Private Clustering via Maximum Coverage](https://mlsanity.com/paper/2008.12388/) (2020)
- [Differentially private k-means clustering via exponential mechanism and max cover](https://mlsanity.com/paper/2009.01220/) (2020)
- [k-variates++: more pluses in the k-means++](https://mlsanity.com/paper/1602.01198/) (2016)
- [Parallel Graph Connectivity in Log Diameter Rounds](https://mlsanity.com/paper/1805.03055/) (2018)

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

- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Clustering and Median Aggregation Improve Differentially Private Inference](https://mlsanity.com/paper/2506.04566/) (2025)
- [Differential Privacy for Clustering Under Continual Observation](https://mlsanity.com/paper/2307.03430/) (2023)
- [Differentially Private Partial Set Cover with Applications to Facility Location](https://mlsanity.com/paper/2207.10240/) (2022)
- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (2023)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)
- [Private Training & Data Generation by Clustering Embeddings](https://mlsanity.com/paper/2506.16661/) (2025)
- [Differentially Private Federated Clustering with Random Rebalancing](https://mlsanity.com/paper/2508.06183/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)
- [On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clustering](https://mlsanity.com/paper/2603.26963/) (2026)

## Abstract (arXiv)

We study the private k-median and k-means clustering problem in d dimensional Euclidean space. By leveraging tree embeddings, we give an efficient and easy to implement algorithm, that is empirically competitive with state of the art non private methods. We prove that our method computes a solution with cost at most O(d3/2log n)· OPT + O(k d2 log2 n / ε2), where ε is the privacy guarantee. (The dimension term, d, can be replaced with O(log k) using standard dimension reduction techniques.) Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical, runs in near-linear, tildeO(nkd), time and scales to tens of millions of points. We also show that our method is amenable to parallelization in large-scale distributed computing environments. In particular we show that our private algorithms can be implemented in logarithmic number of MPC rounds in the sublinear memory regime. Finally, we complement our theoretical analysis with an empirical evaluation demonstrating the algorithm's efficiency and accuracy in comparison to other privacy clustering baselines.