Differentially Private Publication of Sparse Data

By Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, Thanh T. L. Tran. 2011

54 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Functional Mechanism: Regression Analysis under Differential Privacy (2012, methodology): “This section experimentally evaluates the performance of FM against four approaches, namely, DPME [16], Filter-Priority (FP) [7], NoPrivacy , and Truncated .”
Plausible Deniability for Privacy-Preserving Data Synthesis (2017, background): “However, as several researchers have pointed out [12, 29, 6], a direct application is too costly to be practical for high-dimensional datasets due to the complexity of sampling, which grows exponentially in the dimension of the data records.”
PrivBayes: private data release via bayesian networks (2014, background): “For many natural data sets, the domain sizem is orders of magnitude larger than the data size n [15].”
Knowledge-based Systems (2009, unknown): “The best-performing approach is the sequential combination of three proposed methods ( 𝑀𝑂 , 𝑀𝐶 , and 𝑇𝐵 ): V a l u e s”
Differentially Private Spatial Decompositions (2011, methodology): “In our ongoing work, we study other settings: sparse categorical data [3], and higher dimensional data.”
Differentially Private Event Sequences over Infinite Streams (2014, background): “There are also works that focus on other specialized scenarios, such as range-count queries [32, 8], query consistency [19], sparse data [9, 23], correlated queries [18, 21], frequent itemsets [33, 22], trajectories [20], minimization of relative error [31], and non-numerical query answers [26].”
Differentially private histogram publication (2012, background): “[5] develop a general framework to privately release the multi-dimensional sparse data in an efficient way.”