An Iterative Algorithm for Differentially Private Histogram Publication

Traditionally, the accuracy of range queries in differentially private histogram publication was boosted by obtaining the Best Linear Unbiased Estimator (BLUE) of the nodes´ noisy values in the Differential Privacy Range Tree (DPRT). However, exist works require DPRT be perfect k-ary, which means it is not suitable for differentially private histogram publication under arbitrary tree structure. In this paper, we propose an efficient iterative algorithm GBLUE for differential privacy histogram publication based on any tree structure. The correctness of GBLUE is guaranteed by theoretical analysis and experimental demonstration. Experimental results show that GBLUE is effective and feasible.