Data Management

A Learning Theory Approach to Non-Interactive Database Privacy

Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 213.87 KB