计算机科学与探索 ›› 2016, Vol. 10 ›› Issue (6): 786-798.DOI: 10.3778/j.issn.1673-9418.1507067
康 健,吴英杰+,黄泗勇,陈 鸿,孙 岚
KANG Jian, WU Yingjie+, HUANG Siyong, CHEN Hong, SUN Lan
摘要: 现有基于区间树结构的差分隐私直方图发布方法大多采用同方差加噪方式,对其进一步研究发现,采用异方差加噪策略可以进一步提升发布直方图的区间计数查询精度,然而当前基于异方差加噪的差分隐私直方图发布方法对区间树结构却有严格的要求,导致灵活性与实用性较低。为此,提出了一种异方差加噪下面向任意区间树结构的差分隐私直方图发布算法LUE-DPTree(inear unbiased estimator for differential private tree)。首先根据区间计数查询的分布,计算区间树中节点的覆盖概率,并据此分配隐私预算,实现异方差加噪;接着经分析指出该异方差加噪策略适用于任意区间树结构,且从理论上证明了在任意区间树结构下进行异方差加噪后,仍可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差。针对算法的区间计数查询精度及执行效率,与同类算法进行了比较分析。实验结果表明,LUE-DPTree算法是有效可行的。