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

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