[KDD 2022 | 论文简读] 通过分层分离的树实现可扩展的差异私有聚类

简读分享 | 龙文韬 编辑 | 李仲深

论文题目

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