Data Management

A Learning Theory Approach to Non-Interactive Database Privacy

Date Added: Sep 2011
Format: PDF

In this paper, the authors demonstrate that, ignoring computational constraints, it is possible to privately release synthetic databases that are useful for large classes of queries - much larger in size than the database itself. Specifically, they give a mechanism that privately releases synthetic data for a class of queries over a discrete domain with error that grows as a function of the size of the smallest net approximately representing the answers to that class of queries. They show that this in particular implies a mechanism for counting queries that gives error guarantees that grow only with the VC-dimension of the class of queries, which itself grows only logarithmically with the size of the query class.