Patent Issued for Systems and methods to enhance privacy through decision tree based suppression rules on relational databases (USPTO 11960624): Immuta Inc.

2024 MAY 07 (NewsRx) -- By a News Reporter-Staff News Editor at Insurance Daily News -- From Alexandria, Virginia, NewsRx journalists report that a patent by the inventors Murray, John Reilly (Crofton, MD, US), Regensburger, Joseph James (Grove City, OH, US), Rossi, Alfred Vincent (Hilliard, OH, US), Sharp, Mason (Holmdel, NJ, US), filed on February 19, 2021, was published online on April 16, 2024.

The patent’s assignee for patent number 11960624 is Immuta Inc. (College Park, Maryland, United States).

News editors obtained the following quote from the background information supplied by the inventors: “The volume and variety of personal data being recorded and stored by organizations places personal privacy at risk. Regulations such as the Health Insurance Portability and Accountability Act (HIPAA) Privacy Rule, General Data Protection Regulation (GDPR) Recital 26, and European Medicine Agency (EMA) Rule 0070 have been adopted in an effort to protect the privacy of personal data. Each of these regulations require that to avoid restrictions upon sharing and reuse personal data be anonymized or pseudo-anonymized, such that the data cannot reasonably be associated with an individual. Satisfying anonymization requirements is challenging, particularly when considering how identity can be inferred using seemingly innocuous attributes such as birth year, postal code, gender, ethnicity, occupation, etc. These attributes, known as indirect identifiers or quasi-identifiers (QIDs), effectively allow a third party to determine a person’s identity by process of elimination. In order to assess how likely an individual can be re-identified, previous techniques introduced the concept of k-anonymity, which characterizes the degree of protection of the data against such attacks. A dataset is said to have the property of k-anonymity (for the given value of k) where k is defined as the cardinality of the smallest group (or cohort) when the dataset is partitioned into distinct groups of records over all QID values. In some examples, datasets which exhibit k-anonymity can be referred to as k-anonymous. Intuitively, the larger the value of k, the more difficult it is to infer the person associated with a given record, as there are at least k-1 other individuals in the same dataset with matching QIDs.

“Anonymization techniques can be designed to increase k of a dataset, by grouping together similar cohorts to form a large set of indistinguishable records. This is done by either generalizing or suppressing values of certain attributes. For example, generalization techniques for cities could be represented by less specific administrative regions such as counties, states, or countries. Suppression techniques would remove values entirely, for example removing low population zip codes entirely. By affecting the disclosed attributes using generalization and/or suppression, the k-anonymity of a dataset can be increased.

“Existing conventional relational databases typically cannot maintain k-anonymity for responses to queries when the contents of the relational database changes. For many database applications, new records may be continually added and/or deleted from the relational database, which can cause the data anonymity of answers to queries to fall below a desired minimum level; for example, the k value can fall below the desired minimum when a record(s) is removed from or added to the database. Accordingly, what is needed is a system embodying a computer-implemented process that can be utilized to dynamically apply a specified level of k-anonymity to the results or answers to queries sent to a relational database under changing conditions, thus maintaining a desired level of anonymity or privacy regardless of database changes.”

As a supplement to the background information on this patent, NewsRx correspondents also obtained the inventors’ summary information for this patent: “Embodiments consistent with the present invention include systems, processes and computer program products are configured to apply k-anonymity to an answer to a query sent to a relational database. A query to the relational database is obtained, the relational database containing a plurality of records. A frequency of occurrence of the attributes in the relational database is determined, an anonymization rule set is created based on the frequency of occurrence of the attributes, the anonymization rule set defining which attributes are to be suppressed in the answer to the query, the anonymization rule set is used to generate the answer to the query, wherein the answer to the query has k-anonymity, and a display or other device is controlled based on the answer to the query.

“In some embodiments described herein, the anonymization rule set is used by the system to generate the answer to the query having k-anonymity.”

The claims supplied by the inventors are:

“1. A system for anonymizing an answer to a query sent to a relational database, the system comprising: one or more hardware processors; and a non-transitory computer-readable data storage device storing program instructions that, when executed by the one or more hardware processors, cause the system to perform operations comprising: obtaining the query to the relational database, the relational database containing a plurality of records, each of the records having a plurality of attributes pertaining to a unique entity; determining a frequency of occurrence of the attributes in the relational database; creating an anonymization rule set based on the frequency of occurrence of the attributes, the anonymization rule set defining which attributes are to be suppressed in the answer to the query; generating the answer to the query using the anonymization rule set, wherein the answer to the query has k-anonymity; and controlling a display or other device based on the answer to the query.

“2. The system of claim 1, wherein the program instructions further cause the system to perform operations for obtaining a setting for k, where k is a whole number of 2 or greater, and wherein creating the anonymization rule set comprises utilizing the setting for k in creating the anonymization rule set.

“3. The system of claim 2, wherein creating the anonymization rule set based on the frequency of the attributes comprises determining a most frequently occurring one of the attributes in the dataset, and separating the records into a first group of records having the most frequently occurring attribute and a second group of records not having the most frequently occurring attribute.

“4. The system of claim 3, wherein creating the anonymization rule set based on the frequency of the attributes further comprises separating the first group of records and the second group of records into at least one subgroup of records based on values of the attributes other than the most frequently occurring attribute.

“5. The system of claim 4, wherein the setting for k is used to determine a number of the records contained in a smallest group or subgroup of the records.

“6. The system of claim 4, wherein creating the anonymization rule set further comprises placing the first group of records, the second group of records and the subgroups of records into partition elements of a decision tree data structure, and extracting binary conditions for each of the partition elements, the binary conditions for each of the partition elements forming the rule set.

“7. The system of claim 6, wherein the program instructions further cause the system to perform operations for receiving a setting for a maximum tree depth, and using the maximum tree depth to generate the rule set.

“8. The system of claim 1, further comprising applying the rule set to a record pertaining to the query to generate the answer to the query with k-anonymity.

“9. The system of claim 4, wherein the program instructions further cause the system to perform operations for receiving a setting for a maximum policy size, the maximum policy size defining an upper limit of a number of conditions to define a group or a subgroup of the records.

“10. A method for applying k-anonymity to an answer to a query sent to a relational database comprising: obtaining the query to the relational database, the relational database containing a plurality of records, each of the records having a plurality of attributes pertaining to a unique entity; determining a frequency of occurrence of the attributes in the relational database; creating an anonymization rule set based on the frequency of occurrence of the attributes, the anonymization rule set defining which attributes are to be suppressed in the answer to the query; generating the answer to the query using the anonymization rule set, wherein the answer to the query has k-anonymity; and controlling a display or other device based on the answer to the query.

“11. The method of claim 10, further comprising obtaining a setting for k, where k is a whole number of 2 or greater, and wherein creating the anonymization rule set comprises utilizing the setting for k in creating the anonymization rule set.

“12. The method of claim 11, wherein creating the anonymization rule set based on the frequency of the attributes comprises determining a most frequently occurring one of the attributes in the dataset, and separating the records into a first group of records having the most frequently occurring attribute and a second group of records not having the most frequently occurring attribute.

“13. The method of claim 12, wherein creating the anonymization rule set based on the frequency of the attributes further comprises separating the first group of records and the second group of records into a plurality of subgroups of records based on values of the attributes other than the most frequently occurring attribute.

“14. The method of claim 13, wherein creating the anonymization rule set further comprises placing the first group of records, the second group of records and the subgroups of records into partition elements of a decision tree data structure, and extracting binary conditions for each of the partition elements, the binary conditions for each of the partition elements forming the rule set.

“15. The method of claim 14, further comprising receiving a setting for a maximum tree depth, and using the maximum tree depth to generate the anonymization rule set.

“16. The method of claim 13, further comprising using the setting for k to determine a number of the records contained in a smallest group or subgroup of the records.

“17. The method of claim 10, further comprising applying the rule set to a record pertaining to the query to generate the answer to the query with k-anonymity.

“18. The method of claim 13, further comprising receiving a setting for a maximum policy size, the maximum policy size defining an upper limit of a number of conditions to define a group or a subgroup of the records.

“19. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors of a system, cause the system to perform operations comprising: obtaining a query made to a relational database, the relational database containing a plurality of records, each of the records having a plurality of attributes pertaining to a unique entity; determining a frequency of occurrence of the attributes in the relational database; creating an anonymization rule set based on the frequency of occurrence of the attributes, the anonymization rule set defining which attributes are to be suppressed in an answer to the query; generating the answer to the query using the anonymization rule set, wherein the answer to the query has k-anonymity; and controlling a display or other device based on the answer to the query.

“20. The non-transitory computer-readable medium of claim 19, wherein the instructions further cause the system to perform operations comprising determining a most frequently occurring one of the attributes in the dataset, and separating the records into a first group of records having the most frequently occurring attribute and a second group of records not having the most frequently occurring attribute.”

For additional information on this patent, see: Murray, John Reilly. Systems and methods to enhance privacy through decision tree based suppression rules on relational databases. U.S. Patent Number 11960624, filed February 19, 2021, and published online on April 16, 2024. Patent URL (for desktop use only): https://ppubs.uspto.gov/pubwebapp/external.html?q=(11960624)&db=USPAT&type=ids

(Our reports deliver fact-based news of research and discoveries from around the world.)