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.

20 年前的算法经过轻微修改，适用于各种隐私模型，匹配几乎所有已知结果，改进了一些结果并扩展到新的隐私模型，即连续观测环境。

使旧事焕新：差分隐私聚类的统一算法

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

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(d^{3/2}\log n)\cdot OPT + O(k d^2 \log^2 n /
\epsilon^2)$, where $\epsilon$ 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, $\tilde{O}(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.

通过利用树嵌入和标准的降维技术，我们提出了一种高效易实现的算法，能够解决 $k$- 中位数和 $k$- 均值的私有聚类问题，具有很好的时间和空间复杂度，适用于大规模分布式计算环境，并有可观的隐私保障.