loading page

Optimal Mechanisms for Differentially Private Histogram Publication
  • zhanghmtb


Abstract     A histogram is an accurate graphical representation of the distribution of numerical data, which widely used for data publication and data mining and analysis. However, it is likely to leak privacy if we directly use the original data for histogram publication. Differential Privacy(DP), as a mathematical definition, is an ideal solution for releasing the summary data of statistic queries in the database and provides strong guarantees of privacy protection against adversaries with arbitrary background knowledge. Existing studies on DP-compliant histogram mostly concentrate on the tradeoff between the utility and the error, i.e., include the grouping error and the Laplace noise error.In this paper, we propose a new novel mechanism that further reduces the error for boosting the accuracy of computing DP-compliant histogram publication. First, we rely on the algorithm that takes randomized quicksort for summary data which has injected Laplace noise. Second, we propose an optimization of the dynamic programming solution for grouping so that the grouping error can do go lower. We prove the advantage of our approach through comparisons with the competitors. In our experiments, using several real datasets,  confirm that our technique produces the smaller error and considerably improve the accuracy of range queries over histograms.