计算机科学与探索2016，Vol.10Issue(6)：786-798,13.DOI:10.3778/j.issn.1673-9418.1507067
异方差加噪下的差分隐私直方图发布算法
Algorithm for Differential Privacy Histogram Publication with Non-uniform Pri-vate Budget
摘要
Abstract
Most of existing methods for differential privacy histogram publication based on range tree adopt a uniform private budget. However, it is found that the accuracy of range queries can be further enhanced if using a non-uniform private budget. Unfortunately, current techniques for differential privacy histogram publication with non-uniform pri-vate budget require strict range tree structure, which lowers its flexibility and practicability. This paper proposes an algorithm LUE-DPTree (linear unbiased estimator for differential private tree) for differential privacy histogram publi-cation with non-uniform private budget under arbitrary range tree structure. The key idea of LUE-DPTree is to firstly calculate the query coverage probability of range tree nodes based on the distribution of range counting queries so as to allocate the non-uniform private budget. After that, it is shown by further analysis that the strategy of non-uniform pri-vate budget can be used in arbitrary range tree. Furthermore, it is indicated by theoretical proof that, after allocated non-uniform private budget under arbitrary range tree structure, the error of range counting queries still can be further reduced by solving the best linear unbiased estimators of the tree nodes’values through consistency constraint. The experi-mental analysis is designed by comparing LUE-DPTree and the traditional algorithms on the accuracy of range counting queries and the algorithm efficiency. The experimental results show that LUE-DPTree is effective and feasible.关键词
隐私保护/差分隐私/直方图发布/异方差加噪/区间树Key words
privacy preserving/differential privacy/histogram publication/non-uniform private budget/range tree分类
信息技术与安全科学引用本文复制引用
康健,吴英杰,黄泗勇,陈鸿,孙岚..异方差加噪下的差分隐私直方图发布算法[J].计算机科学与探索,2016,10(6):786-798,13.基金项目
The National Natural Science Foundation of China under Grant No.61300026(国家自然科学基金) （国家自然科学基金）
the Natural Science Foundation of Fujian Province under Grant No.2014J01230(福建省自然科学基金) （福建省自然科学基金）
