基于差分隐私的流式直方图发布方法

来源：软件学报杂志2016年第2期北京时间：

作者：张啸剑,孟小峰

单位：张啸剑，河南财经政法大学 计算机与信息工程学院, 河南 郑州 45000211,孟小峰，中国人民大学 信息学院, 北京 10087202

摘要：基于差分隐私保护模型,已经存在多种静态数据集上的直方图发布方法,而目前着重考虑数据流环境下的直方图发布方法却很少.由于数据流本身潜在的复杂性,直接利用现有的满足差分隐私的直方图发布方法处理数据流存在着很多不足,例如发布直方图的可用性低、发布误差大等.基于此,提出了一种基于滑动窗分割的流式直方图发布方法SHP(streaming histogram publication).该方法通过连续分割每个滑动窗中的桶计数,使其构成不同的分组.根据不同的范围计数查询敏感性,提出了3种拉普拉斯噪音添加机制以实现差分隐私保护,分别是滑动窗机制、时间点机制以及自适应抽样机制.在自适应抽样机制中,SHP算法基于当前的滑动窗,依赖于一种自适应抽样方法对下一时刻的计数进行预测,若预测值与真实值的差异小于给定的阈值则发布预测值,否则发布噪音值.该抽样方法可以有效地节省整体的隐私预算.在真实数据集上对SHP算法的可用性进行度量,结果显示,基于抽样的SHP算法的可用性高于另外两种方式.

关键词：差分隐私;数据流;直方图发布;近似误差;拉普拉斯误差

基金资助：国家自然科学基金 (61502146, 61303017, 61202285); 国家高技术研究发展计划(863)(2013AA013204); 高等学校博士学科点专项科研基金(20130004130001); 河南省科技厅基础与前沿技术研究项目(152300410091); 河南省教育厅高等学校重点科研项目(16A520002)