[KDD 2022 | 论文简读] 通过分层分离的树实现可扩展的差异私有聚类
2023-02-18 16:47:53 时间
简读分享 | 龙文韬 编辑 | 李仲深
论文题目
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
相关文章
- Freemarker-数字默认格式化问题
- Chrome扩展插件的开发--获取网页Cookies
- 【以解决】项目使用feign时候提示bean不能注入feign
- Docker设置容器开机自启
- 常用的淘汰算法
- 分布式事务seata,TCC,最大努力通知,最终一致性解决方案——总结三!
- java分布式事务——最终一致性,最大努力通知总结!
- java分布式事务——seata,tcc解决方案总结!
- 分布式系统–拜占庭将军问题(The Byzantine Generals Problem)
- idea中启动SSM项目
- 【编程】给定一个部门,变量出当前部门的所有父部门包含当前部门
- 【解疑】ConcurrentHashMap 在JDK1.7时候put或get时候,怎么定位到数据的?
- Spring的BeanFactoryPostProcessor
- spring注解开发AnnotationConfigApplicationContext的使用
- 匿名内部类方式实现线程的创建
- spring异常:No runnable methods 解决方法
- 基础IO的理解与操作 - fd
- 【图文教程】Centos 7下安装Hadoop-管杀管埋的
- 【Flink教程-已解决】在idea中测试flink的时候,提示读取文件时候错误,提示文件不存在解决方案
- frp 服务器端 frps 一键安装卸载脚本