  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.
