Differentially Private Clustering via Maximum Coverage
Differentially Private Clustering via Maximum Coverage
复制标题
DOI：
10.1609/aaai.v35i13.17375
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Matthew D. Jones;Huy L. Nguyen;Thy Nguyen
中科院分区：
文献类型：
--
作者：
Matthew D. Jones;Huy L. Nguyen;Thy Nguyen
本文研究了度量空间中的聚类问题，同时保持个人数据的隐私。具体来说，我们研究的差异私人的变种的k-中位数和欧几里德k-均值问题。我们提出了多项式算法与常数乘法误差和较低的附加误差比以前的国家的最先进的每个问题。此外，我们的算法使用的聚类算法没有差异隐私作为一个黑盒。这允许从业者通过选择合适的聚类算法来控制运行时间和近似因子之间的权衡。
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.