# US 2024/0005030 A1 · Differentially Private Query Budget Refunding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0005030 A1
- Document ID: US20240005030A1
- Status: Published application
- Kind: A1
- Application number: 18/225,569
- Filed: 2023-07-24
- Published: 2024-01-04
- Earliest claimed: 2019-02-01
- Assignees: Snowflake Inc.
- Applicants: Snowflake Inc.
- Inventors: Christopher Hockenbrocht; Ishaan Nerurkar; Alexander Rozenshteyn; Liam Damewood; David Spies; Mihai Maruseac
- Web page: https://patentgrep.com/patent/US20240005030A1

## CPC

- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06F 16/245: Query processing
- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A differentially private security system communicatively coupled to a database storing restricted data receives a database query from a client. The database query includes a relation specifying a set of data in the database upon which to perform the query and privacy parameters associated with the query. The differentially private security system determines a worst-case privacy spend for the query based on the privacy parameters and the relation. The differentially private security system performs the query upon the set of data specified by the relation and decrements the determined worst-case privacy spend from a privacy budget associated with the client. The differentially private security system records the worst-case privacy spend and the query at a log and determines a privacy budget refund based on queries recorded in the log. The differentially private security system applies the determined privacy budget refund to the privacy budget associated with the client.

## Claims

### Claim 1

(canceled)

### Claim 2

A system comprising:
a processor; and
a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to execute operations comprising:
executing a current query received from a client, the current query comprising a relation that specifies a set of data in a database upon which to execute the current query; and
after executing the current query on the set of data:
recording the current query in a log;
determining whether the relation of the current query is included in any other query previously recorded in the log; and
in response to determining that the relation is not included in any other query previously recorded in the log:
analyzing one or more relationships between the current query and one or more additional queries recorded in the log, the analyzing of the one or more relationships comprising generating a disjointness graph based on the current query and the one or more additional queries;
determining a privacy budget refund for the current query based on the disjointness graph; and
applying the privacy budget refund to a privacy budget associated with the client.

### Claim 3 (depends on 2)

The system of claim 2, 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 different vertex in the set of vertices and representative of a total privacy spend recorded in the log for a select relation represented by the different vertex; and
zero or more edges between pairs of vertices of the set of vertices, each individual edge representing a disjointness of relations represented by a pair of vertices of the individual edge.

### Claim 4 (depends on 3)

The system of claim 3, wherein the determining of the privacy budget refund based on the disjointness graph comprises:
determining a maximum weight independent set of vertices from 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 vertices in the determined maximum weight independent set of vertices;
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 vertices in the determined maximum weight independent set of vertices.

### Claim 5 (depends on 3)

The system of claim 3, wherein the determining of the privacy budget refund based on the disjointness graph comprises:
determining a minimum weight vertex cover of vertices of the disjointness graph 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 vertices in the minimum weight vertex cover of vertices.

### Claim 6 (depends on 2)

The system of claim 2, wherein the operations comprise:
prior to executing the current query on the set of data, determining a worst-case privacy spend for the current query based the relation and a privacy parameter of the current query; and
after executing the current query on the set of data, decrementing the worst-case privacy spend from the privacy budget associated with the client.

### Claim 7 (depends on 6)

The system of claim 6, wherein the operations comprise:
prior to executing the current query on the set of data, recording the worst-case privacy spend with the current query in the log.

### Claim 8 (depends on 6)

The system of claim 6, wherein the operations comprise:
determining whether the worst-case privacy spend exceeds the privacy budget associated with the client, the current query being executed responsive to the worst-case privacy spend not exceeding the privacy budget.

### Claim 9

A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to execute operations comprising:
executing a current query received from a client, the current query comprising a relation that specifies a set of data in a database upon which to execute the current query; and
after executing the current query on the set of data:
recording the current query in a log;
determining whether the relation of the current query is included in any other query previously recorded in the log; and
in response to determining that the relation is not included in any other query previously recorded in the log:
analyzing one or more relationships between the current query and one or more additional queries recorded in the log, the analyzing of the one or more relationships comprising generating a disjointness graph based on the current query and the one or more additional queries;
determining a privacy budget refund for the current query based on the disjointness graph; and
applying the privacy budget refund to a privacy budget associated with the client.

### Claim 10 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, 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 different vertex in the set of vertices and representative of a total privacy spend recorded in the log for a select relation represented by the different vertex; and
zero or more edges between pairs of vertices of the set of vertices, each individual edge representing a disjointness of relations represented by a pair of vertices of the individual edge.

### Claim 11 (depends on 10)

The non-transitory computer-readable storage medium of claim 10, wherein the determining of the privacy budget refund based on the disjointness graph comprises:
determining a maximum weight independent set of vertices from 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 vertices in the determined maximum weight independent set of vertices;
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 vertices in the determined maximum weight independent set of vertices.

### Claim 12 (depends on 10)

The non-transitory computer-readable storage medium of claim 10, wherein the determining of the privacy budget refund based on the disjointness graph comprises:
determining a minimum weight vertex cover of vertices of the disjointness graph 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 vertices in the minimum weight vertex cover of vertices.

### Claim 13 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the operations comprise:
prior to executing the current query on the set of data, determining a worst-case privacy spend for the current query based the relation and a privacy parameter of the current query; and
after executing the current query on the set of data, decrementing the worst-case privacy spend from the privacy budget associated with the client.

### Claim 14 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the operations comprise:
prior to executing the current query on the set of data, recording the worst-case privacy spend with the current query in the log.

### Claim 15 (depends on 13)

The non-transitory computer-readable storage medium of claim 13, wherein the operations comprise:
determining whether the worst-case privacy spend exceeds the privacy budget associated with the client, the current query being executed responsive to the worst-case privacy spend not exceeding the privacy budget.

### Claim 16

A method comprising:
executing, by one or more processors, a current query received from a client, the current query comprising a relation that specifies a set of data in a database upon which to execute the current query; and
after executing the current query on the set of data:
recording, by the one or more processors, the current query in a log;
determining, by the one or more processors, whether the relation of the current query is included in any other query previously recorded in the log; and
in response to determining that the relation is not included in any other query previously recorded in the log:
analyzing, by the one or more processors, one or more relationships between the current query and one or more additional queries recorded in the log, the analyzing of the one or more relationships comprising generating a disjointness graph based on the current query and the one or more additional queries;
determining, by the one or more processors, a privacy budget refund for the current query based on the disjointness graph; and
applying, by the one or more processors, the privacy budget refund to a privacy budget associated with the client.

### Claim 17 (depends on 16)

The method of claim 16, 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 different vertex in the set of vertices and representative of a total privacy spend recorded in the log for a select relation represented by the different vertex; and
zero or more edges between pairs of vertices of the set of vertices, each individual edge representing a disjointness of relations represented by a pair of vertices of the individual edge.

### Claim 18 (depends on 17)

The method of claim 17, wherein the determining of the privacy budget refund based on the disjointness graph comprises:
determining a maximum weight independent set of vertices from 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 vertices in the determined maximum weight independent set of vertices;
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 vertices in the determined maximum weight independent set of vertices.

### Claim 19 (depends on 17)

The method of claim 17, wherein the determining of the privacy budget refund based on the disjointness graph comprises:
determining a minimum weight vertex cover of vertices of the disjointness graph 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 vertices in the minimum weight vertex cover of vertices.

### Claim 20 (depends on 16)

The method of claim 16, comprise:
prior to executing the current query on the set of data, determining, by the one or more processors, a worst-case privacy spend for the current query based the relation and a privacy parameter of the current query; and
after executing the current query on the set of data, decrementing, by the one or more processors, the worst-case privacy spend from the privacy budget associated with the client.

### Claim 21 (depends on 20)

The method of claim 20, comprise:
prior to executing the current query on the set of data, recording, by the one or more processors, the worst-case privacy spend with the current query in the log.
