Differentially private density plots

• US 10,489,605 B2
• Filed: 04/23/2018
• Issued: 11/26/2019
• Est. Priority Date: 11/02/2015
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: LeapYear Technologies, Inc. (Snowflake Inc)
• Inventors: Nerurkar, Ishaan, Hockenbrocht, Christopher, Maruseac, Mihai, Rozenshteyn, Alexander
• Primary Examiner(s): Leung, Robert B
• Application Number:
  US15/960,486
• Publication Number:
  US 20180239925A1
• Time in Patent Office: 582 Days
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence
• CPC Class Codes: H04L 63/105 Multiple levels of security
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]

Abstract

Techniques are described for responding to queries of a private database system. A request is received from a client device to perform a query of the private database system. A level of differential privacy corresponding to the request is identified comprising privacy parameters ε and δ. A set of data stored in the private database system and a set of operations corresponding to the query are identified. The set of operations comprises generating a density plot visualization for one or more subsets of the set of data. The set of data is segmented into disjoint regions. For each disjoint region, a density is identified, and the density is plotted in a differentially private density plot visualization using one or more graphical elements.

Claims

1. A method, comprising:

receiving a request from a client device to perform a query of a private database system;

identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ε and

δ

;

identifying a set of data stored in the private database system and a set of operations to be performed on the set of data corresponding to the requested query;

modifying the set of operations 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;

performing the modified set of operations based on the identified level of differential privacy such that a performance of the set of operations produces a result set that is (ε

,δ

)-differentially private, where performing the modified set of operations comprises segmenting the result set into disjoint regions and for each disjoint region;

determining a density of the disjoint region; and

plotting the density for the disjoint region in a differentially private density plot visualization, the visualization using a graphical element determined responsive to the determined density; and

providing the differentially private density plot visualization to the client device for display on a hardware display of the client device.

2. The method of claim 1, wherein segmenting the result set into disjoint regions comprises:

identifying loci corresponding to the request, the loci specifying boundaries of the disjoint regions; and

segmenting the set of data into the disjoint regions responsive to the identified loci.

3. The method of claim 1, wherein determining the density of the disjoint region comprises:

performing a differentially private count for the disjoint region based on the identified level of differential privacy; and

determining the density of the disjoint region based on the differentially private count.

4. The method of claim 1, wherein determining the density of the disjoint region comprises:

performing a two-dimensional private wavelet transform for the disjoint region; and

determining the density of the disjoint region based on the two-dimensional private wavelet transform.

5. The method of claim 1, wherein the visualization distinguishes different densities using different variations of the graphical element.

6. The method of claim 1, wherein determining the density of the disjoint region comprises:

comparing a differentially private count for the disjoint region to a threshold value; and

determining the density of the disjoint region responsive to the comparison.

7. The method of claim 6, wherein the threshold value is based on confidence intervals on Laplace noise within the differentially private count performed upon each disjoint region.

8. A system comprising:

a processor for executing computer program instructions; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations comprising;

receiving a request from a client device to perform a query of a private database system;

identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ε and

δ

;

identifying a set of data stored in the private database system and a set of operations to be performed on the set of data corresponding to the requested query;

modifying the set of operations 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;

performing the modified set of operations based on the identified level of differential privacy such that a performance of the set of operations produces a result set that is (ε

,δ

)-differentially private, where performing the modified set of operations comprises segmenting the result set into disjoint regions and for each disjoint region;

determining a density of the disjoint region; and

plotting the density for the disjoint region in a differentially private density plot visualization, the visualization using a graphical element determined responsive to the determined density; and

providing the differentially private density plot visualization to the client device for display on a hardware display of the client device.

9. The system of claim 8, wherein segmenting the result set into disjoint regions comprises:

identifying loci corresponding to the request, the loci specifying boundaries of the disjoint regions; and

segmenting the set of data into the disjoint regions responsive to the identified loci.

10. The system of claim 8, wherein determining the density of the disjoint region comprises:

performing a differentially private count for the disjoint region based on the identified level of differential privacy; and

determining the density of the disjoint region based on the differentially private count.

11. The system of claim 8, wherein determining the density of the disjoint region comprises:

performing a two-dimensional private wavelet transform for the disjoint region; and

determining the density of the disjoint region based on the two-dimensional private wavelet transform.

12. The system of claim 8, wherein the visualization distinguishes different densities using different variations of the graphical element.

13. The system of claim 8, wherein determining the density of the disjoint region comprises:

comparing a differentially private count for the disjoint region to a threshold value; and

determining the density of the disjoint region responsive to the comparison.

14. The system of claim 13, wherein the threshold value is based on confidence intervals on Laplace noise within the differentially private count performed upon each disjoint region.

15. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations including:

receiving a request from a client device to perform a query of a private database system;

identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ε and

δ

;

identifying a set of data stored in the private database system and a set of operations to be performed on the set of data corresponding to the requested query;

modifying the set of operations 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;

performing the modified set of operations based on the identified level of differential privacy such that a performance of the set of operations produces a result set that is (ε

,δ

)-differentially private, where performing the modified set of operations comprises segmenting the result set into disjoint regions and for each disjoint region;

determining a density of the disjoint region; and

plotting the density for the disjoint region in a differentially private density plot visualization, the visualization using a graphical element determined responsive to the determined density; and

providing the differentially private density plot visualization to the client device for display on a hardware display of the client device.

16. The non-transitory computer-readable storage medium of claim 15, wherein segmenting the result set into disjoint regions comprises:

identifying loci corresponding to the request, the loci specifying boundaries of the disjoint regions; and

segmenting the set of data into the disjoint regions responsive to the identified loci.

17. The non-transitory computer-readable storage medium of claim 15, wherein determining the density of the disjoint region comprises:

performing a differentially private count for the disjoint region based on the identified level of differential privacy; and

determining the density of the disjoint region based on the differentially private count.

18. The non-transitory computer-readable storage medium of claim 15, wherein determining the density of the disjoint region comprises:

performing a two-dimensional private wavelet transform for the disjoint region; and

determining the density of the disjoint region based on the two-dimensional private wavelet transform.

19. The non-transitory computer-readable storage medium of claim 15, wherein the visualization distinguishes different densities using different variations of the graphical element.

20. The non-transitory computer-readable storage medium of claim 15, wherein determining the density of the disjoint region comprises:

comparing a differentially private count for the disjoint region to a threshold value; and

determining the density of the disjoint region responsive to the comparison.