论文标题
通过最大覆盖范围差异私人聚类
Differentially Private Clustering via Maximum Coverage
论文作者
论文摘要
本文研究了在度量空间中聚类的问题，同时保留了单个数据的隐私。具体而言，我们检查了K-Medians和Euclidean 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.
