Differentially Private Histogram Publishing through Lossy Compression

Abstract : Differential privacy has emerged as one of the most promising privacy models for private data release. It can be used to release different types of data, and, in particular, histograms, which provide useful summaries of a dataset. Several differentially private histogram releasing schemes have been proposed recently. However, most of them directly add noise to the histogram counts, resulting in undesirable accuracy. In this paper, we propose two sanitization techniques that exploit the inherent redundancy of real-life datasets in order to boost the accuracy of histograms. They lossily compress the data and sanitize the compressed data. Our first scheme is an optimization of the Fourier Perturbation Algorithm (FPA) presented in [13]. It improves the accuracy of the initial FPA by a factor of 10. The other scheme relies on clustering and exploits the redundancy between bins. Our extensive experimental evaluation over various real-life and synthetic datasets demonstrates that our techniques preserve very accurate distributions and considerably improve the accuracy of range queries over attributed histograms.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-00747821
Contributor : Claude Castelluccia <>
Submitted on : Friday, November 2, 2012 - 11:02:37 AM
Last modification on : Thursday, July 26, 2018 - 2:08:02 PM

Links full text

Identifiers

Collections

Citation

Claude Castelluccia, Gergely Acs, Chen Rui. Differentially Private Histogram Publishing through Lossy Compression. ICDM 2012 - 12th IEEE International Conference on Data Mining, Dec 2012, Brussels, Belgium. pp.1-10, ⟨10.1109/ICDM.2012.80⟩. ⟨hal-00747821⟩

Share

Metrics

Record views

177