CONSISTENT CONTINGENCY TABLE RELEASE
Techniques for contingency table release provide an accurate and consistent set of tables while guaranteeing that privacy is preserved. A positive and integral database is constructed that corresponds to these tables. Therefore, a database can be generated that preserves low-order marginals up to a small error. Moreover, a gracefully degrading version of the results is provided as a database can be computed such that the error in the low-order marginals is small, and increases smoothly with the order of the marginal.
1 . A contingency table release method, comprising:
determining a first data set based on a first contingency table;
determining a plurality of Fourier coefficients based on the first data set, the Fourier coefficients comprising noise;
solving a linear program based on the Fourier coefficients to generate a solution;
generating a second contingency table based on the solution of the linear program; and
outputting a second data set based on the second contingency table.
2 . The method of claim 1 , wherein the noise is Laplace noise.
3 . The method of claim 1 , further comprising receiving a query prior to determining the first data set, wherein the second data set is a result of the query.
4 . The method of claim 1 , wherein the first data set comprises a plurality of marginals.
5 . The method of claim 4 , further comprising identifying a plurality of Fourier vectors based on the marginals, wherein determining the Fourier coefficients is based on the Fourier vectors.
6 . The method of claim 5 , wherein identifying the Fourier vectors comprises determining a downward closure to the marginals.
7 . The method of claim 5 , further comprising computing an inner product of the Fourier vectors and Laplace noise.
8 . The method of claim 4 , wherein the second data set comprises a further plurality of marginals.
9 . The method of claim 1 , further comprising rounding the solution of the linear program to nearest integrals, wherein generating the second contingency table uses the nearest integrals.
10 . The method of claim 1 , wherein the second data set has the properties of privacy, accuracy, and consistency.
11 . A query processing method, comprising:
receiving a query;
generating a first contingency table responsive to the query;
generating a second contingency table responsive to the first contingency table; and
outputting a result to the query based on the second contingency table, the result having the properties of privacy, accuracy, and consistency.
12 . The method of claim 11 , wherein generating the second contingency table comprises solving a linear program using data based on the first contingency table.
13 . The method of claim 12 , wherein the data based on the first contingency table comprises a set of noisy marginals.
14 . The method of claim 11 , wherein generating the second contingency table comprises converting data based on the first contingency table to a Fourier domain and computing the second contingency table in the Fourier domain.
15 . The method of claim 11 , wherein generating the second contingency table comprises converting a plurality of marginals of the first contingency table to a plurality of Fourier coefficients in a Fourier domain and applying a linear program to the Fourier coefficients.
16 . The method of claim 11 , wherein the second contingency table is non-negative.
17 . A contingency table release system, comprising:
a user interface module that receives a query; and
a query analyzer and processor that generates a first contingency table responsive to the query, generates a second contingency table responsive to the first contingency table, and generates data based on the second contingency table, the data having the properties of privacy, accuracy, and consistency.
18 . The system of claim 17 , wherein the query analyzer and processor solves a linear program to generate the second contingency table.
19 . The system of claim 17 , wherein the query analyzer and processor performs a computation on data based on the first contingency table in a Fourier domain.
20 . The system of claim 19 , wherein the query analyzer and processor uses Laplace noise in the computation on the data based on the first contingency table in the Fourier domain.