异方差加噪下的差分隐私直方图发布算法

摘要：

现有基于区间树结构的差分隐私直方图发布方法大多采用同方差加噪方式，对其进一步研究发现，采用异方差加噪策略可以进一步提升发布直方图的区间计数查询精度，然而当前基于异方差加噪的差分隐私直方图发布方法对区间树结构却有严格的要求，导致灵活性与实用性较低。为此，提出了一种异方差加噪下面向任意区间树结构的差分隐私直方图发布算法LUE-DPTree（inear unbiased estimator for differential private tree）。首先根据区间计数查询的分布，计算区间树中节点的覆盖概率，并据此分配隐私预算，实现异方差加噪；接着经分析指出该异方差加噪策略适用于任意区间树结构，且从理论上证明了在任意区间树结构下进行异方差加噪后，仍可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差。针对算法的区间计数查询精度及执行效率，与同类算法进行了比较分析。实验结果表明，LUE-DPTree算法是有效可行的。

关键词：隐私保护、差分隐私、直方图发布、异方差加噪、区间树

所属期刊栏目：10

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

资助基金：The National Natural Science Foundation of China under Grant No.61300026;the Natural Science Foundation of Fujian Province under Grant No.2014J01230

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

页数：共13页

页码：786-798