mlsanityData to 14 Oct 2026

Making Old Things New: A Unified Algorithm for Differentially Private Clustering

arXiv 2406.11649 ↗First posted 17 Jun 2024cs.DS cs.CR cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithms: the landscape of private clustering algorithms is therefore quite intricate. In this paper, we show that a 20-year-old algorithm can be slightly modified to work for any of these models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them and extend it to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 14 of its 44 references that are in the map. First posted on arXiv 17 Jun 2024.

Builds on

14 of 44 references.

References · 14

  1. 2019The Privacy Blanket of the Shuffle Modelcited by 74
  2. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  3. 2019SoK: Differential Privaciescited by 34
  4. 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
  5. 2021The Price of Differential Privacy under Continual Observationcited by 34
  6. 2018Differentially Private k-Means with Constant Multiplicative Errorcited by 22
  7. 2021Locally Private k-Means in One Roundcited by 19
  8. 2021Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Messagecited by 18
  9. 2020Connecting Robust Shuffle Privacy and Pan-Privacycited by 12
  10. 2021Differentially Private Algorithms for Graphs Under Continual Observationcited by 12
  11. 2013Communication Steps for Parallel Query Processingcited by 11
  12. 2020A note on differentially private clustering with large additive errorcited by 4
2 more
  1. 2021Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Errorcited by 1
  2. 2023Differentially Private Clustering in Data Streamscited by 1

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Binned Group Algebra Factorization for Differentially Private Continual Countingcited by 3