Differentially Private Clustering via Maximum Coverage

Authors

  • Matthew Jones Northeastern University
  • Huy L. Nguyen Northeastern University
  • Thy D Nguyen Northeastern University

Keywords:

Privacy & Security

Abstract

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.

Downloads

Published

2021-05-18

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17375

Issue

Section

AAAI Technical Track on Philosophy and Ethics of AI