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.
Type de document :
Communication dans un congrès
ICDM 2012 - 12th IEEE International Conference on Data Mining, Dec 2012, Brussels, Belgium. IEEE, Data Mining (ICDM), 2012 IEEE 12th International Conference on, pp.1-10, 2012, 〈10.1109/ICDM.2012.80〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00747821
Contributeur : Claude Castelluccia <>
Soumis le : vendredi 2 novembre 2012 - 11:02:37
Dernière modification le : mercredi 11 avril 2018 - 01:54:44

Lien texte intégral

Identifiants

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. IEEE, Data Mining (ICDM), 2012 IEEE 12th International Conference on, pp.1-10, 2012, 〈10.1109/ICDM.2012.80〉. 〈hal-00747821〉

Partager

Métriques

Consultations de la notice

167