Differentially private query budget refunding

1. A method for refunding privacy spend to a client based on a query by the client to a database storing restricted data, the method comprising:

receiving a database query from the client, the database query including a relation specifying a set of data in the database upon which to perform the query and privacy parameters;

determining a worst-case privacy spend for the query based on the privacy parameters and the relation;

performing the query upon the set of data specified by the relation;

decrementing the determined worst-case privacy spend from a privacy budget associated with the client;

recording the worst-case privacy spend and the performed query at a log;

determining a privacy budget refund after performing the query based on the worst-case privacy spend of the performed query and privacy spends of one or more additional queries recorded in the log; and

applying the determined privacy budget refund to the privacy budget associated with the client,

wherein determining the privacy budget refund comprises:

analyzing relationships among the performed query and the one or more additional queries recorded in the log,

wherein analyzing the relationships comprises analyzing a measure of disjointness generated based on the performed query and one of the one or more additional queries in the log; and

determining the privacy budget refund based on the analysis of the relationships and the worst-case privacy spend of the performed query and of the privacy spends of the one or more additional queries.

2. The method of claim 1 , further comprising:

performing a subsequent query subsequent to the performed query and prior to determining the privacy budget refund; and

recording the subsequent query in the log prior to determining the privacy budget refund;

wherein determining the privacy budget refund is based in part on the subsequent query.

3. The method of claim 1 , wherein analyzing the relationships among the performed query and the one or more additional queries recorded in the log comprises:

generating a disjointness graph based on the performed query and the one or more additional queries in the log, wherein the disjointness graph is a weighted undirected graph comprising:

a set of vertices each representing a relation in the log;

a set of vertex weights each associated with a vertex in the set of vertices and representative of a total privacy spend recorded in the log for the relation represented by the associated vertex; and

zero or more edges between pairs of vertices of the set of vertices, each edge between a pair of vertices representing a disjointness of the relations represented by the pair of vertices; and

wherein determining the privacy budget refund based on the analysis of the relationships and the worst-case privacy spend of the performed query and of the privacy spends of the one or more additional queries comprises determining the privacy budget refund based on the disjointness graph.

4. The method of claim 3 , wherein determining the privacy budget refund based on the disjointness graph comprises:

determining a maximum weight independent set among the vertices of the set of vertices based on the zero or more edges and the set of vertex weights;

determining a sum of the vertex weights associated with the vertices in the determined maximum weight independent set;

determining a total privacy spend of all queries in the log; and

determining the privacy budget refund as a difference between the total privacy spend of all queries in the log and the determined sum of the vertex weights associated with the vertices in the determined maximum weight independent set.

5. The method of claim 3 , wherein determining the privacy budget refund based on the disjointness graph comprises:

determining a minimum weight vertex cover among the set of vertex weights based on the zero or more edges and the set of vertex weights; and

determining the privacy budget refund as a sum of the vertex weights associated with the vertices in the minimum weight vertex cover.

6. The method of claim 1 , further comprising:

determining whether the worst-case privacy spend exceeds the privacy budget;

wherein the query is performed responsive to the worst-case privacy spend not exceeding the privacy budget.

7. The method of claim 6 , wherein the privacy budget includes a soft budget and a hard budget, wherein determining whether the worst-case privacy spend exceeds the privacy budget comprises:

determining whether the worst-case privacy spend exceeds the hard budget; and

responsive to determining the worst-case privacy spend does not exceed the hard budget, determining whether the soft budget is already exceeded;

wherein the query is performed responsive to determining that the soft budget is not already exceeded.

8. The method of claim 1 , further comprising:

comparing the relation in the performed query to relations in the one or more additional queries in the log; and

based on the comparison of the relation in the performed query to relations in the one or more additional queries in the log, determining whether the relation in the performed query is a new relation in the log;

wherein determining the privacy budget refund and applying the privacy budget refund are responsive to the relation being a new relation in the log.

9. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations for refunding privacy spend to a client based on a query by the client to a database storing restricted data, the operations comprising:

receiving a database query from the client, the database query including a relation specifying a set of data in the database upon which to perform the query and privacy parameters;

determining a worst-case privacy spend for the query based on the privacy parameters and the relation;

performing the query upon the set of data specified by the relation;

decrementing the determined worst-case privacy spend from a privacy budget associated with the client;

recording the worst-case privacy spend and the performed query at a log;

determining a privacy budget refund after performing the query based on the worst-case privacy spend of the performed query and privacy spends of one or more additional queries recorded in the log; and

applying the determined privacy budget refund to the privacy budget associated with the client,

wherein determining the privacy budget refund comprises:

analyzing relationships among the performed query and the one or more additional queries recorded in the log,

wherein analyzing the relationships comprises analyzing a measure of disjointness generated based on the performed query and one of the one or more additional queries in the log; and

determining the privacy budget refund based on the analysis of the relationships and the worst-case privacy spend of the performed query and of the privacy spends of the one or more additional queries.

10. The non-transitory computer-readable storage medium of claim 9 , wherein analyzing the relationships among the performed query and the one or more additional queries recorded in the log comprises:

generating a disjointness graph based on the performed query and the one or more additional queries in the log, wherein the disjointness graph is a weighted undirected graph comprising:

a set of vertices each representing a relation in the log;

a set of vertex weights each associated with a vertex in the set of vertices and representative of a total privacy spend recorded in the log for the relation represented by the associated vertex; and

zero or more edges between pairs of vertices of the set of vertices, each edge between a pair of vertices representing a disjointness of the relations represented by the pair of vertices; and

wherein determining the privacy budget refund based on the analysis of the relationships and the worst-case privacy spend of the performed query and of the privacy spends of the one or more additional queries comprises determining the privacy budget refund based on the disjointness graph.

11. The non-transitory computer-readable storage medium of claim 10 , wherein determining the privacy budget refund based on the disjointness graph comprises:

determining a maximum weight independent set among the vertices of the set of vertices based on the zero or more edges and the set of vertex weights;

determining a sum of the vertex weights associated with the vertices in the determined maximum weight independent set;

determining a total privacy spend of all queries in the log; and

determining the privacy budget refund as a difference between the total privacy spend of all queries in the log and the determined sum of the vertex weights associated with the vertices in the determined maximum weight independent set.

12. The non-transitory computer-readable storage medium of claim 10 , wherein determining the privacy budget refund based on the disjointness graph comprises:

determining a minimum weight vertex cover among the set of vertex weights based on the zero or more edges and the set of vertex weights; and

determining the privacy budget refund as a sum of the vertex weights associated with the vertices in the minimum weight vertex cover.

13. The non-transitory computer-readable storage medium of claim 9 , the operations further comprising:

determining whether the worst-case privacy spend exceeds the privacy budget;

wherein the query is performed responsive to the worst-case privacy spend not exceeding the privacy budget.

14. The non-transitory computer-readable storage medium of claim 13 , wherein the privacy budget includes a soft budget and a hard budget, wherein determining whether the worst-case privacy spend exceeds the privacy budget comprises:

determining whether the worst-case privacy spend exceeds the hard budget; and

responsive to determining the worst-case privacy spend does not exceed the hard budget, determining whether the soft budget is already exceeded;

wherein the query is performed responsive to determining that the soft budget is not already exceeded.

15. The non-transitory computer-readable storage medium of claim 9 , further comprising:

comparing the relation in the performed query to relations in the one or more additional queries in the log; and

based on the comparison of the relation in the performed query to relations in the one or more additional queries in the log, determining whether the relation in the performed query is a new relation in the log;

wherein determining the privacy budget refund and applying the privacy budget refund are responsive to the relation being a new relation in the log.

16. A system, comprising:

a processor; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations for refunding privacy spend to a client based on a query by the client to a database storing restricted data, the operations comprising:

receiving a database query from the client, the database query including a relation specifying a set of data in the database upon which to perform the query and privacy parameters;

determining a worst-case privacy spend for the query based on the privacy parameters and the relation;

performing the query upon the set of data specified by the relation;

decrementing the determined worst-case privacy spend from a privacy budget associated with the client;

recording the worst-case privacy spend and the performed query at a log;

determining a privacy budget refund after performing the query based on the worst-case privacy spend of the performed query and privacy spends of one or more additional queries recorded in the log; and

applying the determined privacy budget refund to the privacy budget associated with the client,

wherein determining the privacy budget refund comprises:

analyzing relationships among the performed query and the one or more additional queries recorded in the log,

wherein analyzing the relationships

 comprises analyzing a measure of disjointness generated based on the performed query and one of the one or more additional queries in the log; and

determining the privacy budget refund based on the analysis of the relationships and the worst-case privacy spend of the performed query and of the privacy spends of the one or more additional queries.

17. The system of claim 16 , wherein analyzing the relationships among the performed query and the one or more additional queries recorded in the log comprises:

generating a disjointness graph based on the performed query and the one or more additional queries in the log, wherein the disjointness graph is a weighted undirected graph comprising:

a set of vertices each representing a relation in the log;

a set of vertex weights each associated with a vertex in the set of vertices and representative of a total privacy spend recorded in the log for the relation represented by the associated vertex; and

zero or more edges between pairs of vertices of the set of vertices, each edge between a pair of vertices representing a disjointness of the relations represented by the pair of vertices; and

wherein determining the privacy budget refund based on the analysis of the relationships and the worst-case privacy spend of the performed query and of the privacy spends of the one or more additional queries comprises determining the privacy budget refund based on the disjointness graph.

18. The system of claim 17 , wherein determining the privacy budget refund based on the disjointness graph comprises:

determining a maximum weight independent set among the vertices of the set of vertices based on the zero or more edges and the set of vertex weights;

determining a sum of the vertex weights associated with the vertices in the determined maximum weight independent set;

determining a total privacy spend of all queries in the log; and

determining the privacy budget refund as a difference between the total privacy spend of all queries in the log and the determined sum of the vertex weights associated with the vertices in the determined maximum weight independent set.