前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[KDD 2022 | 论文简读] 通过分层分离的树实现可扩展的差异私有聚类

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

作者头像
智能生信
发布2022-12-29 17:31:39
3510
发布2022-12-29 17:31:39
举报
文章被收录于专栏:智能生信

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

论文题目

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-12-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 智能生信 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档