Differentially Private Clustering via Maximum Coverage

No. 13: AAAI-21 Technical Tracks 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Philosophy and Ethics of AI

This paper studies the problem of clustering in metric spaces while preserving the privacy of individual data. Specifically, we examine differentially private variants of the k-medians and Euclidean k-means problems. We present polynomial algorithms with constant multiplicative error and lower additive error than the previous state-of-the-art for each problem. Additionally, our algorithms use a clustering algorithm without differential privacy as a black-box. This allows practitioners to control the trade-off between runtime and approximation factor by choosing a suitable clustering algorithm to use.

10.1609/aaai.v35i13.17375