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

摘要：

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

关键词：差分隐私、直方图发布、分组、拉普拉斯误差、近似误差

所属期刊栏目：53

分类号：TP392(计算技术、计算机技术)

资助基金：国家自然科学基金项目61502146，61379050，U1404605，61202285；国家“八六三”高技术研究发展计划基金项目2013AA013204；河南省科技厅基础与前沿技术研究项目152300410091；河南省教育厅高等学校重点科研项目16A520002；河南财经政法大学校重大研究课题201426 This work was supported by the National Natural61502146，61379050，U1404605，61202285;the National High Technology Research and Development Program of China 863 Program 2013AA013204;the Basic Research Program of Henan Science and Technology Department152300410091;the Key Research Program of the Higher Education of Henan Educational Committee16A520002;the Key Research Program of Henan University of Economics and Law 201426．

在线出版日期：2016-06-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：1106-1117