Differentially Private Clustering via Maximum Coverage
Keywords:Privacy & Security
AbstractThis 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.
How to Cite
Jones, M., Nguyen, H. L., & Nguyen, T. D. (2021). Differentially Private Clustering via Maximum Coverage. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11555-11563. https://doi.org/10.1609/aaai.v35i13.17375
AAAI Technical Track on Philosophy and Ethics of AI