Full Citation

Title: Output Perturbation with Query Relaxation

Citation Type: Journal Article

Publication Year: 2008

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: 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 relaxationmechanism, which removes the restriction on the number of permissible queries. The effectiveness and efficiency of our solution are verified through experiments with real data.

User Submitted?: No

Authors: Tao, Yufei; Xiao, Xiaokui

Periodical (Full): Proceedings of the VLDB Endowment

Issue: 1

Volume: 3

Pages: 857-869

Data Collections: IPUMS USA

Topics: Methodology and Data Collection

Countries: