Calculating differentially private queries using local sensitivity on time variant databases

Abstract

Systems, methods, and manufactures for enhancing the determination of differential privacy query results. A computer implemented method for enhancing the determination of differential privacy query results is provided. The computer implemented method includes obtaining a first query of a database, determining a query result by executing the first query on the database, determining a noisy result by adding noise to the query result, wherein the noise is determined based on a first statistical evaluation of the first query, determining a first hash value identifying the first query based on one or more of the first statistical evaluation and a second statistical evaluation of the first query, maintaining the noisy result linked to the first hash value in a result cache, and returning the noisy result from the result cache in response to a subsequent query when a second hash value identifying the subsequent query is determined to be statistically similar to the first hash value.

What is claimed is: 
     
         1 . A computer implemented method for enhancing the determination of differential privacy query results, the computer implemented method comprising:
 obtaining a first query of a database;   determining a query result by executing the first query on the database;   determining a noisy result by adding noise to the query result, wherein the noise is determined based on a first statistical evaluation of the first query;   determining a first hash value identifying the first query based on one or more of the first statistical evaluation and a second statistical evaluation of the first query;   maintaining the noisy result linked to the first hash value in a result cache; and   returning the noisy result from the result cache in response to a subsequent query when a second hash value identifying the subsequent query is determined to be statistically similar to the first hash value.   
     
     
         2 . The computer implemented method of  claim 1 , further comprising:
 determining that the result cache lacks any query results of previous queries that are substantially equivalent to the first query; and   in response to the determining, partitioning the database into a plurality of groups, wherein the first query is executed on the plurality of groups.   
     
     
         3 . The computer implemented method of  claim 2 , wherein the partitioning is performed using one or more sampling methods selected from: a purely random sampling, a stratified sampling, and a quota based sampling. 
     
     
         4 . The computer implemented method of  claim 2 , further comprising, prior to the partitioning, determining whether a specificity of the first query exceeds a predetermined specificity threshold, and
 if the specificity exceeds the predetermined specificity threshold, returning a request for a revised query.   
     
     
         5 . The computer implemented method of  claim 2 , wherein the partitioning is performed using a distributed query engine. 
     
     
         6 . The computer implemented method of  claim 1 , wherein at least one of the first or second statistical evaluations comprise:
 determining a sensitivity of the first query; and   determining a nominal measurement of the first query, wherein the noise and the first hash value are based on one or more of the sensitivity and the nominal measurement.   
     
     
         7 . The computer implemented method of  claim 1 , wherein the noisy result is maintained in the result cache for a predetermined time period. 
     
     
         8 . The computer implemented method of  claim 1 , wherein metadata of the first query is stored with the noisy result in the result cache. 
     
     
         9 . The computer implemented method of  claim 8 , wherein the metadata includes one or more of a timestamp, geospatial data, and an Application Program Interface (API) key. 
     
     
         10 . The computer implemented method of  claim 1 , wherein the result cache comprises a memory location distinct from the database. 
     
     
         11 . A system for enhancing the determination of differential privacy query results, the system comprising:
 a database;   a result cache;   a processor; and   a computer-readable data storage device storing program instructions that, when executed by the processor, cause the system to perform operations comprising:   receiving a first query for data in the database;   determining a query result by executing the first query on the database;   determining a noisy result by adding noise to the query result, wherein the noise is determined based on a first statistical evaluation of the first query;   determining a first hash value identifying the first query based on one or more of the first statistical evaluation and a second statistical evaluation of the first query;   maintaining the noisy result linked to the first hash value in the result cache; and   returning the noisy result from the result cache in response to a subsequent query when a second hash value identifying the subsequent query is determined to be statistically similar to the first hash value.   
     
     
         12 . The system of  claim 11 , wherein the operations further comprise:
 determining that the result cache lacks any query results of previous queries that are substantially equivalent to the first query; and   in response to the determining, partitioning the database into a plurality of groups, wherein the first query is executed on the plurality of groups.   
     
     
         13 . The system of  claim 12 , wherein the partitioning is performed using one or more sampling methods, selected from a purely random sampling, a stratified sampling, and a quota based sampling. 
     
     
         14 . The system of  claim 12 , wherein the operations further comprise: prior to the partitioning, determining whether a specificity of the first query exceeds a predetermined specificity threshold, and
 if the specificity exceeds the predetermined specificity threshold, returning a request for a revised query.   
     
     
         15 . The system of  claim 12 , wherein the partitioning is performed using a distributed query engine. 
     
     
         16 . The system of  claim 11 , wherein the noisy result is maintained in the result cache for a predetermined time period. 
     
     
         17 . The system of  claim 11 ,
 wherein at least one of the first or second statistical evaluations comprise:   determining a sensitivity of the first query; and   determining a nominal measurement of the first query, wherein the noise and the first hash value are based on one or more of the sensitivity and the nominal measurement.   
     
     
         18 . The system of  claim 11 , wherein metadata of the first query is stored with the noisy result in the result cache. 
     
     
         19 . The system of  claim 18 , wherein the metadata includes one or more of a timestamp, geospatial data, and an Application Program Interface (API) key. 
     
     
         20 . The system of  claim 11 , wherein the result cache comprises a memory location distinct from the database.