Translated Title
Algorithm for Differential Privacy Histogram Publication with Non-uniform Pri-vate Budget
Translated 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.
Translated Keyword
differential privacy
histogram publication
non-uniform private budget
privacy preserving
range tree
Access Number
WF:perioarticaljsjkxyts201606007
