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$- 均值的私有聚类问题，具有很好的时间和空间复杂度，适用于大规模分布式计算环境，并有可观的隐私保障.