Differentially Private Publication of Sparse Data

Details Differentially Private Publication of Sparse Data Differentially Private Publication of Sparse Data

2011-03-04

arxiv.org/abs/1103.0825v1

Computer Science

Databases

Scientific paper

The problem of privately releasing data is to provide a version of a dataset without revealing sensitive information about the individuals who contribute to the data. The model of differential privacy allows such private release while providing strong guarantees on the output. A basic mechanism achieves differential privacy by adding noise to the frequency counts in the contingency tables (or, a subset of the count data cube) derived from the dataset. However, when the dataset is sparse in its underlying space, as is the case for most multi-attribute relations, then the effect of adding noise is to vastly increase the size of the published data: it implicitly creates a huge number of dummy data points to mask the true data, making it almost impossible to work with. We present techniques to overcome this roadblock and allow efficient private release of sparse data, while maintaining the guarantees of differential privacy. Our approach is to release a compact summary of the noisy data. Generating the noisy data and then summarizing it would still be very costly, so we show how to shortcut this step, and instead directly generate the summary from the input data, without materializing the vast intermediate noisy data. We instantiate this outline for a variety of sampling and filtering methods, and show how to use the resulting summary for approximate, private, query answering. Our experimental study shows that this is an effective, practical solution, with comparable and occasionally improved utility over the costly materialization approach.

Affiliated with

Also associated with

No associations

Rating

Differentially Private Publication of Sparse Data does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Differentially Private Publication of Sparse Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Differentially Private Publication of Sparse Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-320391