基于差分隐私的流式直方图发布方法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

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


Streaming Histogram Publication Method with Differential Privacy
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61502146, 61303017, 61202285); National High-Tech R&D Program of China (863) (2013AA013204); Research Fund for the Doctoral Program of Higher Education of China (20130004130001); Basic Research Program of He’nan Science and Technology Department (152300410091); Research Program of the Higher Education of He’nan Educational Committee (16A520002)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Various approaches have been proposed to release histogram on static datasets with differential privacy, while little work exist that handle dynamic datasets. Those existing static approaches are ill-suited for the practical applications on data stream due to the inherent complexity of publishing streaming histograms. With this consideration, this paper addresses the challenge by proposing a partitioning-based method, called SHP (streaming histogram publication), which partitions the count values of each sliding window into different groups for releasing the final histogram. In view of different global sensitivity of queries adopted by this paper, three incremental utility-based mechanisms for adding Laplace noise are proposed to achieve differential privacy. The three mechanisms are sliding window mechanism, time point mechanism, and adaptive sampling mechanism, respectively. In the third mechanism, SHP relies on the adaptive sampling method to predict the next arriving count value at non-sampling time points. If the difference between the predicted value and the true value is less than a user-defined threshold, then it releases the predicted value, otherwise, releases the true value. This mechanism can save privacy budget in terms of sampling interval updates. Experimental results or real datasets show that the utility of SHP based on sampling is better than the other two mechanisms.

    参考文献
    相似文献
    引证文献
引用本文

张啸剑,孟小峰.基于差分隐私的流式直方图发布方法.软件学报,2016,27(2):381-393

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2014-03-30
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2016-02-03
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号