# US 11,113,413 B2 · Calculating differentially private queries using local sensitivity on time variant databases > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,413 B2 - Document ID: US11113413B2 - Status: Granted - Kind: B2 - Application number: 16/112,035 - Filed: 2018-08-24 - Published: 2019-02-28 - Granted: 2021-09-07 - Earliest claimed: 2017-08-25 - Assignees: Immuta, Inc. - Applicants: Immuta, Inc. - Inventors: James Leonard Klucar, Jr.; Kyle Lilly; Joseph Regensburger; Steven Touw - Web page: https://patentgrep.com/patent/US11113413B2 ## CPC - G06F 21/6227: {where protection concerns the structure of data, e.g. records, types, queries} - G06F 16/2455: Query execution - G06F 16/24552: {Database cache management} - G06F 16/24554: {Unary operations; Data partitioning operations} - G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems, methods, and manufactures for enhancing the determination of differential privacy query results. Implementations may include a database; a result cache; a processor; and a media storing instructions that, when executed by the processor, cause the system to perform operations that include obtaining a query of the database; determining that a specificity of the query exceeds a specificity threshold; determining that the result cache lacks any query results of previous queries that are substantially equivalent to the query; partitioning the database into a plurality of groups; determining a query result by executing the 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 and the nominal measurement; storing the noisy result in the result cache; and providing the noisy result in response to the query. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 1) The system of claim 1, wherein adding noise to the query result comprises generating a randomized result using a Sample and Aggregate (SA) framework. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) The system of claim 1, wherein the virtualized database comprises personal information of individuals. ### Claim 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. ### Claim 10 (depends on 9) The system according to claim 9, comprising automatically scaling the added noise to obscure new observations qualified as outliers within the database. ### Claim 11 (depends on 9) The system according to claim 9, wherein the added noise is proportional to a maximum sensitivity introduced by an entire dataset in the database. ### Claim 12 (depends on 9) 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. ### Claim 13 (depends on 9) 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. ### Claim 14 (depends on 13) 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. ### Claim 15 (depends on 9) 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 9) 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. ### Claim 18 (depends on 9) The system of claim 9, wherein the virtualized database comprises personal information of individuals.