mlsanityData to 14 Oct 2026

Locally Private k-Means in One Round

arXiv 2104.09734 ↗First posted 20 Apr 2021cs.DS cs.CR cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

We provide an approximation algorithm for k-means clustering in the one-round (aka non-interactive) local model of differential privacy (DP). This algorithm achieves an approximation ratio arbitrarily close to the best non private approximation algorithm, improving upon previously known algorithms that only guarantee large (constant) approximation ratios. Furthermore, this is the first constant-factor approximation algorithm for k-means that requires only one round of communication in the local DP model, positively resolving an open question of Stemmer (SODA 2020). Our algorithmic framework is quite flexible; we demonstrate this by showing that it also yields a similar near-optimal approximation algorithm in the (one-round) shuffle DP model.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 26 of its 72 references that are in the map. First posted on arXiv 20 Apr 2021.

Builds on

26 of 72 references.

References · 26

  1. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 272
  2. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 164
  3. 2017Collecting Telemetry Data Privatelycited by 149
  4. 2020The Discrete Gaussian for Differential Privacycited by 135
  5. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 128
  6. 2018Distributed Differential Privacy via Shufflingcited by 115
  7. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  8. 2019The Privacy Blanket of the Shuffle Modelcited by 74
  9. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  10. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  11. 2020Private Summation in the Multi-Message Shuffle Modelcited by 34
  12. 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
14 more
  1. 2017Practical Locally Private Heavy Hitterscited by 29
  2. 2015Differentially Private k-Means Clusteringcited by 27
  3. 2018Differentially Private k-Means with Constant Multiplicative Errorcited by 22
  4. 2016Locating a Small Cluster Privatelycited by 20
  5. 2017Clustering Algorithms for the Centralized and Local Modelscited by 18
  6. 2019Separating Local & Shuffled Differential Privacy via Histogramscited by 16
  7. 2019Locally Private k-Means Clusteringcited by 15
  8. 2019Private Aggregation from Fewer Anonymous Messagescited by 15
  9. 2020Pure Differentially Private Summation from Anonymous Messagescited by 15
  10. 2020Connecting Robust Shuffle Privacy and Pan-Privacycited by 12
  11. 2020Differentially Private Clustering via Maximum Coveragecited by 9
  12. 2020Differentially private k-means clustering via exponential mechanism and max covercited by 8
  13. 2020On Distributed Differential Privacy and Counting Distinct Elementscited by 8
  14. 2016k-variates++: more pluses in the k-means++cited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 6; 2024: 2; 2025: 4; 2026: 1.

19 papers.

Sort:

  1. 2022Orchestra: Unsupervised Federated Learning via Globally Consistent Clusteringcited by 45
  2. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  3. 2022Differentially Private Vertical Federated Clusteringcited by 10
  4. 2023Towards Unbiased Training in Federated Open-world Semi-supervised Learningcited by 7
  5. 2022Near-Optimal Correlation Clustering with Privacycited by 6
  6. 2022Graph Generative Model for Benchmarking Graph Neural Networkscited by 6
  7. 2025Urania: Differentially Private Insights into AI Usecited by 4
  8. 2025Learning from End User Data with Shuffled Differential Privacy over Kernel Densitiescited by 3
  9. 2023Multi-Message Shuffled Privacy in Federated Learningcited by 2
  10. 2023Differential Privacy for Clustering Under Continual Observationcited by 2
  11. 2024FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacycited by 2
  12. 2021Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Errorcited by 1
7 more
  1. 2023DPM: Clustering Sensitive Data through Separationcited by 1
  2. 2023Differentially Private Clustering in Data Streamscited by 1
  3. 2024Making Old Things New: A Unified Algorithm for Differentially Private Clusteringcited by 1
  4. 2025Differentially Private In-Context Learning with Nearest Neighbor Searchcited by 1
  5. 2023Improving the Utility of Differentially Private Clustering through Dynamical Processingcited by 0
  6. 2025Differentially Private Federated Clustering with Random Rebalancingcited by 0
  7. 2026On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clusteringcited by 0