Compressive mechanism: utilizing sparse representation in differential privacy

By Yang D. Li, Zhenjie Zhang, Marianne S. Winslett, Y. Yang. 2011

85 citations recorded by the source corpus.

Differential privacy provides the first theoretical foundation with provable privacy guarantee against adversaries with arbitrary prior knowledge. The main idea to achieve differential privacy is to inject random noise into statistical query results. Besides correctness, the most important goal in the design of a differentially private mechanism is to reduce the effect of random noise, ensuring that the noisy results can still be useful. This paper proposes the compressive mechanism, a novel solution on the basis of state-of-the-art compression technique, called compressive sensing. Compressive sensing is a decent theoretical tool for compact synopsis construction, using random projections. In this paper, we show that the amount of noise is significantly reduced from O(n) to O(log(n)), when the noise insertion procedure is carried on the synopsis samples instead of the original database. As an extension, we also apply the proposed compressive mechanism to solve the problem of continual release of statistical results. Extensive experiments using real datasets justify our accuracy claims.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Functional Mechanism: Regression Analysis under Differential Privacy (2012, methodology): “…error of a given set of count queries; Barak et al. [2] and Ding et al. [8] consider the publication of data cubes; Xu et al. [31] and Li et al. [18] focus on publishing histograms; McSherry and Mironov [20], Rastogi and Nath [24], and McSherry and Mahajan [19] devise methods for re-leasing…”
Privacy via the Johnson-Lindenstrauss Transform (2012, background): “[29], shows that through the use of compressed sensing techniques to produce a small synopsis of the original database, subsequent addition of Laplacian noise, and decoding of the obtained noisy synopsis, one can obtain a privacy-preserving version of the original data.”
Location Privacy Protection Based on Differential Privacy Strategy for Big Data in Industrial Internet of Things (2018, methodology): “The DP-topk method is proposed in [24], which has a more rigorous definition of”
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].”
Differential privacy based on importance weighting (2013, background): “Some researchers consider deletion or addition of an entry (Hay et al. 2010; Mohammed et al. 2011), while others consider only replacement (Chaudhuri et al. 2011; Li et al. 2011).”
Differential Privacy and Machine Learning: a Survey and Review (2014, background): “[35] assumes that the data matrix is sparse, thus the mechanism can make use of results from compressive sensing research.”