简读分享 | 龙文韬 编辑 | 李仲深
论文题目
Scalable Differentially Private Clustering via Hierarchically Separated Trees
论文摘要
作者研究了d维欧几里得空间中的私有k中值和k均值聚类问题。通过利用树嵌入,作者给出了一种高效且易于实现的算法,该算法对于最先进的非私有方法具有竞争力。作者证明,该方法计算的解决方案的成本最多为𝑂(𝑑^(3/2)log𝑛) ·𝑂𝑃𝑇 +𝑂(𝑘𝑑^2log^2 𝑛/𝜖^2),,其中ε是隐私保证。(使用标准降维技术将维度项d替换为 O(log k)。)虽然最坏情况比最先进的私有聚类方法差,但作者提出的算法是实用的,运行时间接近线性Õ(nkd),可扩展到数千万数据。作者还表明,该方法适合在大规模分布式计算环境中并行化。特别是,作者展示了该私有算法可以在次线性记忆体制下以对数数量的MPC轮实现。最后,作者通过实证评估来补充作者的理论分析,证明了与其他聚类基线相比,该算法的高效率和准确性。
论文链接
https://doi.org/10.1145/3534678.3539409