Advanced Search
    Zhang Xiaojian, Shao Chao, Meng Xiaofeng. Accurate Histogram Release under Differential Privacy[J]. Journal of Computer Research and Development, 2016, 53(5): 1106-1117. DOI: 10.7544/issn1000-1239.2016.20150304
    Citation: Zhang Xiaojian, Shao Chao, Meng Xiaofeng. Accurate Histogram Release under Differential Privacy[J]. Journal of Computer Research and Development, 2016, 53(5): 1106-1117. DOI: 10.7544/issn1000-1239.2016.20150304

    Accurate Histogram Release under Differential Privacy

    • Grouping-based differentially private histogram release has attracted considerable research attention in recent years. The trade-off between approximation error caused by the group’s mean and Laplace error due to Laplace noise constrains the accuracy of histogram release. Most existing methods based on grouping strategy cannot efficiently accommodate the both errors. This paper proposes an efficient differentially private method, called DiffHR (differentially private histogram release) to publish histograms. In order to boost the accuracy of the released histogram, DiffHR employs Metropolis-Hastings method in MCMC (Markov chain Monte Carlo) and the exponential mechanism to propose an efficient sorting method. This method generates a differentially private histogram by sampling and exchanging two buckets to approximate the correct order. To balance Laplace error and approximation error efficiently, a utility-driven adaptive clustering method is proposed in DiffHR to partition the sorted histogram. Furthermore, the time complexity of the clustering method is O(n). DiffHR is compared with existing methods such as GS, AHP on the real datasets. The experimental results show that DiffHR outperforms its competitors, and achieves the accurate results.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return