Calculating differentially private queries using local sensitivity on time variant databases

1. A system for enhancing the determination of differential privacy query results, the system comprising:

a database;

a result cache;

one or more processors; and

a computer-readable data storage device storing program instructions that, when executed by the one or more processors, cause the system to perform operations comprising:

obtaining a first query of the database;

determining that a specificity of the first query exceeds a specificity threshold;

determining that the result cache lacks any query results of previous queries that are substantially equivalent to the first query;

partitioning the database into a plurality of groups;

determining a query result by executing the first query on the plurality of groups;

determining a sensitivity of the query and a nominal measurement of the query;

determining a noisy result by adding noise to the query result based on the sensitivity of the query and the nominal measurement of the query;

storing the noisy result in the result cache with a hash value generated using the first query, the sensitivity of the query, and the nominal measurement of the query;

providing the noisy result in response to the first query;

determining in response to a subsequent query that the result cache includes query results substantially equivalent to the subsequent query based at least on the hash value; and

providing the noisy result from the result cache in response to the subsequent query.

2. The system of claim 1 further comprising determining whether a query is executed over a dataset with sufficient size to be divided into statistically equivalent groups.

3. The system of claim 2 , wherein determining if a query can be divided into statistically equivalent groups is measured using a statistical test of equivalence such as counting, ANOVA, or other tests for equivalence.

4. The system of claim 1 , wherein determining that the result cache lacks any query results of previous queries that are substantially equivalent to the first query comprises determining whether one or more of the query results of previous queries are stale.

5. The system of claim 4 , wherein determining whether one or more of the query results of previous queries are stale comprises determining that a predetermined period has passed since determination of the one or more query results of the previous queries.

6. The system of claim 1 , wherein adding noise to the query result comprises generating a randomized result using a Sample and Aggregate (SA) framework.

7. The system of claim 1 , wherein the database comprises a virtualized database comprising a single data structure configured to present a plurality of data sources as a single data source.

8. The system of claim 1 , wherein the virtualized database comprises personal information of individuals.

9. A system for enhancing the determination of differential privacy query results, the system comprising:

a database;

a result cache;

one or more processors; and

a computer-readable data storage device storing program instructions that, when executed by the one or more processors, cause the system to perform operations comprising:

obtaining a first query of the database;

determining that a specificity of the first query exceeds a specificity threshold;

determining that the result cache lacks any query results of previous queries that are substantially equivalent to the first query;

partitioning the database into a plurality of groups;

determining a query result by executing the first query on the plurality of groups;

determining a sensitivity of the query and a nominal measurement of the query;

determining a noisy result by adding noise to the query result based on the sensitivity of the query and the nominal measurement of the query;

storing the noisy result in the result cache with a hash value generated using the first query, the sensitivity of the query, and the nominal measurement of the query;

providing the noisy result in response to the first query; and

maintaining the noisy result in the result cache for a predetermined period of time for providing in response to one or more subsequently obtained queries of the database based on the hash value and a second hash value of the one or more subsequently obtained queries.

10. The system according to claim 9 , comprising automatically scaling the added noise to obscure new observations qualified as outliers within the database.

11. The system according to claim 9 , wherein the added noise is proportional to a maximum sensitivity introduced by an entire dataset in the database.

12. The system according to claim 9 , wherein the determining the noisy result comprises:

drawing a sample from a stochastic distribution, the one or more samples centered at the nominal measurement of the query; and

adding noise to the sample.

13. The system of claim 9 further comprising determining whether a query is executed over a dataset with sufficient size to be divided into statistically equivalent groups.

14. The system of claim 13 , wherein determining if a query can be divided into statistically equivalent groups is measured using a statistical test of equivalence such as counting, ANOVA, or other tests for equivalence.

15. The system of claim 9 , wherein determining that the result cache lacks any query results of previous queries that are substantially equivalent to the first query comprises determining whether one or more of the query results of previous queries are stale.

16. The system of claim 15 , wherein determining whether one or more of the query results of previous queries are stale comprises determining that a predetermined period has passed since determination of the one or more query results of the previous queries.

17. The system of claim 9 , wherein the database comprises a virtualized database comprising a single data structure configured to present a plurality of data sources as a single data source.

18. The system of claim 9 , wherein the virtualized database comprises personal information of individuals.