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 private 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 publication 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 private 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 experimental 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

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

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