Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-18
WPES '11 Proceedings of the 10th annual ACM workshop on Privacy in the electronic society ACM New York, NY, USA (2011), pages
Computer Science
Data Structures and Algorithms
20 pages, 6 figures
Scientific paper
10.1145/2046556.2046581
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 \emph{compressive mechanism}, a novel solution on the basis of state-of-the-art compression technique, called \emph{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(\sqrt{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.
Li Yang D.
Winslett Marianne
Yang Yin
Zhang Zhenjie
No associations
LandOfFree
Compressive Mechanism: Utilizing Sparse Representation in Differential Privacy 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 Compressive Mechanism: Utilizing Sparse Representation in Differential Privacy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressive Mechanism: Utilizing Sparse Representation in Differential Privacy will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-270914