差分隐私下一种精确直方图发布方法

作     者：张啸剑 邵超 孟小峰 Zhang Xiaojian;Shao Chao;Meng Xiaofeng

作者机构：河南财经政法大学计算机与信息工程学院郑州450002 中国人民大学信息学院北京100872 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2016年第53卷第5期

页      面：1106-1117页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 0839[工学-网络空间安全] 081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(61502146 61379050 U1404605 61202285) 国家"八六三"高技术研究发展计划基金项目(2013AA013204) 河南省科技厅基础与前沿技术研究项目(152300410091) 河南省教育厅高等学校重点科研项目(16A520002) 河南财经政法大学校重大研究课题(201426)~~ 

主　　题：差分隐私 直方图发布 分组 拉普拉斯误差 近似误差 

摘      要：基于分组的差分隐私直方图发布得到了研究者的广泛关注,组均值造成的近似误差与噪音造成的拉普拉斯误差之间的均衡直接制约着直方图发布精度,针对现有基于分组的直方图发布方法难以有效兼顾近似误差与拉普拉斯误差的不足,提出了一种满足差分隐私的精确直方图发布方法DiffHR(differentially private histogram release);通过分析直方图桶计数序列的排序有助于提升发布精度,利用Markov链蒙特卡洛(Markov chain Monte Carlo,MCMC)方法中的Metropolis-Hastings技术与指数机制,提出了一种有效排序方法,通过不断置换2个随机选取的桶以逐渐逼近正确排序;基于抽样排序后的直方图,提出了一种基于懒散分组下界的自适应贪心聚类方法,该方法的时间复杂度为O(n),并且可有效均衡近似误差与拉普拉斯误差.DiffHR,GS,AHP方法在真实数据上的实验结果表明,其发布精度上优于同类算法.