Skip to Main content Skip to Navigation
New interface
Conference papers

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
Complete list of metadata
Contributor : Claude Castelluccia Connect in order to contact the contributor
Submitted on : Friday, November 2, 2012 - 11:02:37 AM
Last modification on : Saturday, December 10, 2022 - 3:57:14 AM

Links full text



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⟩



Record views