Scalable Differentially Private Clustering via Hierarchically Separated Trees - Sorbonne Université Access content directly
Conference Papers Year : 2022

Scalable Differentially Private Clustering via Hierarchically Separated Trees

Abstract

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/2 log n)⁆ OPT + O(kd2 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, Õ (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.

Dates and versions

hal-03944623 , version 1 (18-01-2023)

Identifiers

Cite

Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz Medina, et al.. Scalable Differentially Private Clustering via Hierarchically Separated Trees. KDD '22: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Aug 2022, Washington DC, United States. pp.221-230, ⟨10.1145/3534678.3539409⟩. ⟨hal-03944623⟩
19 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More