Differentially Private Histogram Publishing through Lossy Compression

Claude Castelluccia 1 Gergely Acs 1 Chen Rui
1 PLANETE - Protocols and applications for the Internet
Inria Grenoble - Rhône-Alpes, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Type de document :
Communication dans un congrès
International Conference Data Mining, Dec 2012, Brussels, Belgium. 2012
Liste complète des métadonnées

Contributeur : Claude Castelluccia <>
Soumis le : vendredi 2 novembre 2012 - 11:02:37
Dernière modification le : jeudi 11 janvier 2018 - 16:25:40


  • HAL Id : hal-00747821, version 1



Claude Castelluccia, Gergely Acs, Chen Rui. Differentially Private Histogram Publishing through Lossy Compression. International Conference Data Mining, Dec 2012, Brussels, Belgium. 2012. 〈hal-00747821〉



Consultations de la notice