Output perturbation with query relaxation

Given a dataset containing sensitive personal information, a statistical database answers aggregate queries in a manner that preserves individual privacy. We consider the problem of constructing a statistical database using output perturbation , which protects privacy by injecting a small noise into each query result. We show that the state-of-the-art approach, ε- differential privacy , suffers from two severe deficiencies: it (i) incurs prohibitive computation overhead, and (ii) can answer only a limited number of queries, after which the statistical database has to be shut down. To remedy the problem, we develop a new technique that enforces ε-different privacy with economical cost. Our technique also incorporates a query relaxation mechanism, which removes the restriction on the number of permissible queries. The effectiveness and efficiency of our solution are verified through experiments with real data.