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

来源：计算机研究与发展杂志2016年第5期北京时间：

作者：张啸剑,邵超,孟小峰,

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

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