# US 12,223,083 B2 · Differentially private processing and database storage

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

- Number: US 12,223,083 B2
- Document ID: US12223083B2
- Status: Granted
- Kind: B2
- Application number: 18/225,573
- Filed: 2023-07-24
- Published: 2024-01-11
- Granted: 2025-02-11
- Earliest claimed: 2015-11-02
- Assignees: Snowflake Inc.
- Applicants: Snowflake Inc.
- Inventors: Ishaan Nerurkar; Christopher Hockenbrocht; Liam Damewood; Mihai Maruseac; Alexander Rozenshteyn
- Web page: https://patentgrep.com/patent/US12223083B2

## CPC

- G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries}
- G06F 16/24547: {Optimisations to support specific applications; Extensibility of optimisers}
- G06F 16/2455: Query execution
- G06F 16/2462: {Approximate or statistical queries}
- G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases}
- G06F 16/248: Presentation of query results
- G06F 16/25: Integrating or interfacing systems involving database management systems
- G06F 21/6218: {to a system of files or objects, e.g. local or distributed file system or database}
- G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes}
- G06F 21/6254: {by anonymising data, e.g. decorrelating personal data from the owner's identification}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 20/00: Machine learning
- G06N 20/20: Ensemble learning
- H04L 63/105: {Multiple levels of security}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A hardware database privacy device is communicatively coupled to a private database system. The hardware database privacy device receives a request from a client device to perform a query of the private database system and identifies a level of differential privacy corresponding to the request. The identified level of differential privacy includes privacy parameters (ε,δ) indicating the degree of information released about the private database system. The hardware database privacy device identifies a set of operations to be performed on the set of data that corresponds to the requested query. After the set of data is accessed, the set of operations is modified based on the identified level of differential privacy such that a performance of the modified set of operations produces a result set that is (ε,δ)-differentially private.

## Claims

### Claim 1

A system comprising:
a processor configured to execute computer program instructions; and
a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform actions comprising:
receiving a database query requesting a differentially private response to the database query;
determining a privacy parameter associated with the database query, the privacy parameter describing a degree of information to release about a set of data stored by the system that is responsive to the database query;
identifying a privacy budget associated with the database query, the privacy budget describing a degree of information available to be released about data by the system;
decrementing the privacy budget by a first spend determined responsive to the database query; and
responsive to the database query, performing the database query by performing a differentially private set of operations on the set of data stored by the system to produce a differentially private result set that releases a certain degree of information about the set of data based on the privacy parameter, each entry in a subset of the set of data being labeled with a category chosen from a set of two or more categories, the differentially private set of operations comprising:
generating an output vector by applying a trained classifier to entries of the subset, each element of the output vector corresponding to a numerical output of the trained classifier for a corresponding entry in the subset;
identifying a threshold value and assigning categories to each element of the output vector based on a perturbed threshold value; and
recording counts related to a performance of the trained classifier, the counts generated by comparing the assigned categories of the elements of the output vector to the corresponding label in the subset.

### Claim 2 (depends on 1)

The system of claim 1, wherein the differentially private set of operations comprises:
identifying a loss function for the set of data, the loss function comprising a function of a set of parameters θ that describes correlations in the set of data; and
minimizing a perturbed loss function over the set of parameters θ, and the differentially private set of operations comprising perturbing the loss function by a factor defined by:
θ
T
⁢
υ
⁡
(
G
⁡
(
4
·
K
2
·
R
2
2
·
(
log
⁢
2
δ
+
ϵ
)
ϵ
2
)
)
,
to produce the set of parameters θ that minimizes the perturbed loss function, wherein K and R2 are constants, ϵ is the first spend, δ is another privacy parameter, and v( ) denotes a vector populated with one or more random variables.

### Claim 3 (depends on 1)

The system of claim 1, wherein the subset of the set of data is a first subset of the set of data, wherein the differentially private set of operations comprises an interquartile range operation on a second subset of the set of data, and wherein the differentially private set of operations comprises perturbing a result of the interquartile range operation by a factor defined by:
(
1
1
+
log
⁢
n
)
L
⁡
(
c
2
ϵ
3
)
,
to produce the differentially private result set, wherein Lis a zero-centered Laplacian random variable, c2 and n are constants, and ϵ2 is a second spend.

### Claim 4 (depends on 1)

The system of claim 1, wherein the subset of the set of data is a first subset of the set of data, and wherein the differentially private set of operations comprises:
identifying a loss function for a second subset of the set of data, the loss function a function of a set of parameters θ describing correlations in the second subset; and
for at least one time step, generating an estimate for the set of parameters θ that minimize the loss function, and wherein the differentially private set of operations comprises for each time step, perturbing the estimate for the set of parameters θ by:
η
t
·
υ
⁡
(
G
⁡
(
c
1
2
·
n
2
·
(
log
⁢
n
δ
+
log
⁢
1
δ
)
ϵ
4
)
)
,
to produce the perturbed estimate of the set of parameters θ as the differentially private result set, wherein nt, n, and c1 are constants, and ϵ2 is a second spend, G( ) denotes a zero-centered Gaussian random variable and v( ) denotes a vector populated with one or more random variables.

### Claim 5 (depends on 1)

The system of claim 1,
wherein the differentially private set of operations comprises:
perturbing the threshold value based on a second spend to generate the perturbed threshold value; and
perturbing counts relating to performance of the trained classifier based on the second spend to produce the perturbed counts as the differentially private result set.

### Claim 6 (depends on 1)

The system of claim 1, wherein the differentially private set of operations is performed responsive to determining that the privacy budget accommodates the first spend.

### Claim 7 (depends on 1)

The system of claim 1, wherein the privacy budget is associated with a user of the system.

### Claim 8

A method comprising:
receiving, by one or more processors, a database query requesting a differentially private response to the database query;
determining, by the one or more processors, a privacy parameter associated with the database query, the privacy parameter describing a degree of information to release about a set of data stored by a database system that is responsive to the database query;
identifying, by the one or more processors, a privacy budget associated with the database query, the privacy budget describing a degree of information available to be released about data by the database system;
decrementing, by the one or more processors, the privacy budget by a first spend determined responsive to the database query; and
responsive to the database query, performing the database query, by the one or more processors, by performing a differentially private set of operations on the set of data stored by the database system to produce a differentially private result set that releases a certain degree of information about the set of data based on the privacy parameter, each entry in a subset of the set of data being labeled with a category chosen from a set of two or more categories, the differentially private set of operations comprising:
generating an output vector by applying a trained classifier to entries of the subset, each element of the output vector corresponding to a numerical output of the trained classifier for a corresponding entry in the subset;
identifying a threshold value and assigning categories to each element of the output vector based on a perturbed threshold value; and
recording counts related to a performance of the trained classifier, the counts generated by comparing the assigned categories of the elements of the output vector to the corresponding label in the subset.

### Claim 9 (depends on 8)

The method of claim 8, wherein the differentially private set of operations comprises:
identifying a loss function for the set of data, the loss function comprising a function of a set of parameters θ that describes correlations in the set of data; and
minimizing a perturbed loss function over the set of parameters θ, and the differentially private set of operations comprising perturbing the loss function by a factor defined by:
θ
T
⁢
υ
⁡
(
G
⁡
(
4
·
K
2
·
R
3
2
·
(
log
⁢
1
δ
+
ϵ
)
ϵ
2
)
)
,
to produce the set of parameters θ that minimizes the perturbed loss function, wherein K and R2 are constants, ϵ is the first spend, δ is another privacy parameter, and v( ) denotes a vector populated with one or more random variables.

### Claim 10 (depends on 8)

The method of claim 8, wherein the subset of the set of data is a first subset of the set of data, wherein the differentially private set of operations comprises an interquartile range operation on a second subset of the set of data, and wherein the differentially private set of operations comprises perturbing a result of the interquartile range operation by a factor defined by:
(
1
1
+
log
⁢
n
)
L
⁡
(
c
2
ϵ
3
)
,
to produce the differentially private result set, wherein Lis a zero-centered Laplacian random variable, c2 and n are constants, and ϵ2 is a second spend.

### Claim 11 (depends on 8)

The method of claim 8, wherein the subset of the set of data is a first subset of the set of data, and wherein the differentially private set of operations comprises:
identifying a loss function for a second subset of the set of data, the loss function a function of a set of parameters θ describing correlations in the second subset; and
for at least one time step, generating an estimate for the set of parameters θ that minimize the loss function, and wherein the differentially private set of operations comprises for each time step, perturbing the estimate for the set of parameters θ by:
η
t
·
υ
⁡
(
G
⁡
(
c
1
2
·
n
2
·
(
log
⁢
n
δ
+
log
⁢
1
δ
)
ϵ
4
)
)
,
to produce the perturbed estimate of the set of parameters θ as the differentially private result set, wherein nt, n, and c1 are constants, and ϵ2 is a second spend, G( ) denotes a zero-centered Gaussian random variable and v( ) denotes a vector populated with one or more random variables.

### Claim 12 (depends on 8)

The method of claim 8,
wherein the differentially private set of operations comprises:
perturbing the threshold value based on a second spend to generate the perturbed threshold value; and
perturbing counts relating to performance of the trained classifier based on the second spend to produce the perturbed counts as the differentially private result set.

### Claim 13 (depends on 8)

The method of claim 8, wherein the differentially private set of operations is performed responsive to determining that the privacy budget accommodates the first spend.

### Claim 14 (depends on 8)

The method of claim 8, wherein the privacy budget is associated with a user of the database system.

### Claim 15

A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform actions for implementing differential privacy comprising:
receiving a database query requesting a differentially private response to the database query;
determining a privacy parameter associated with the database query, the privacy parameter describing a degree of information to release about a set of data stored by a database system that is responsive to the database query;
identifying a privacy budget associated with the database query, the privacy budget describing a degree of information available to be released about data by the database system;
decrementing the privacy budget by a first spend determined responsive to the database query; and
responsive to the database query, performing the database query by performing a differentially private set of operations on the set of data stored by the database system to produce a differentially private result set that releases a certain degree of information about the set of data based on the privacy parameter, the differentially private set of operations comprising a median operation on elements associated with a subset of the set of data, each entry in a subset of the set of data being labeled with a category chosen from a set of two or more categories, the differentially private set of operations comprising:
generating an output vector by applying a trained classifier to entries of the subset, each element of the output vector corresponding to a numerical output of the trained classifier for a corresponding entry in the subset;
identifying a threshold value and assigning categories to each element of the output vector based on a perturbed threshold value; and
recording counts related to a performance of the trained classifier, the counts generated by comparing the assigned categories of the elements of the output vector to the corresponding label in the subset.

### Claim 16 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the differentially private set of operations comprises:
identifying a loss function for the set of data, the loss function comprising a function of a set of parameters θ that describes correlations in the set of data; and
minimizing a perturbed loss function over the set of parameters θ, and the differentially private set of operations comprising perturbing the loss function by a factor defined by:
θ
T
⁢
υ
⁡
(
G
⁡
(
4
·
K
2
·
R
3
2
·
(
log
⁢
1
δ
+
ϵ
)
ϵ
2
)
)
,
to produce the set of parameters θ that minimizes the perturbed loss function, wherein K and R2 are constants, ϵ is the first spend, δ is another privacy parameter, and v( ) denotes a vector populated with one or more random variables.

### Claim 17 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the subset of the set of data is a first subset of the set of data, wherein the differentially private set of operations comprises an interquartile range operation on a second subset of the set of data, and wherein the differentially private set of operations comprises perturbing a result of the interquartile range operation by a factor defined by:
(
1
1
+
log
⁢
n
)
L
⁡
(
c
2
ϵ
3
)
,
to produce the differentially private result set, wherein Lis a zero-centered Laplacian random variable, c2 and n are constants, and ϵ2 is a second spend.

### Claim 18 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the differentially private set of operations comprises:
perturbing the threshold value based on a second spend to generate the perturbed threshold value; and
perturbing counts relating to performance of the trained classifier based on the second spend to produce the perturbed counts as the differentially private result set.