Data de-identification with minimal data change operations to maintain privacy and data utility
AssigneeInternational Business Machines Corporation
InventorAris Gkoulalas-Divanis
Life of this patent
Estimating the term…
Abstract
Methods, systems, and computer program products are provided for producing de-identified data from a dataset. A first set of constraints are determined based on anonymity requirements from a privacy model. A second set of constraints are determined based on knowledge hiding requirements. A model is generated to determine minimum loss of analytic utility in the dataset for de-identification while satisfying the first set of constraints and the second set of constraints. The model is applied to the dataset to determine changes to the dataset for de-identification that satisfy the first set of constraints and the second set of constraints. De-identified data is produced by modifying the dataset in accordance with the determined changes.
Claims6
A system for producing de-identified data from a dataset, the system comprising:
- at least one processor;
- and
- at least one memory connected with the at least one processor, wherein the at least one processor is configured to perform:
- determining a first set of constraints based on anonymity requirements from a privacy model, each record of the dataset having an anonymity constraint of the first set of constraints;
- determining a second set of constraints based on knowledge hiding requirements, each constraint of the second set of constraints corresponding to a respective pattern to be concealed in the de-identified data;
- generating a model to determine minimum loss of analytic utility in the dataset for de-identification while satisfying the first set of constraints and the second set of constraints, the generating the model further comprising:
- selectively replacing items in each constraint of the first set of constraints and items in each constraint of the second set of constraints with binary variables used by a constraint satisfaction problem, wherein each of the binary variables indicates either a presence or an absence of a corresponding item in the de-identified data, and
- assigning a value to each of the binary variables such that the first set of constraints and the second set of constraints are satisfied and a sum of all of the binary variables of the constraint satisfaction problem is maximized;
- applying the model to the dataset to determine changes to the dataset for de-identification that satisfy the first set of constraints and the second set of constraints, the applying the model further comprising:
- formulating and solving the constraint satisfaction problem, and
- determining ones of items of the dataset to be changed based on values of the binary variables of the constraint satisfaction problem;
- and
- producing the de-identified data by modifying the dataset in accordance with the determined changes.
A computer program product comprising at least one computer readable storage medium having computer readable program code embodied therewith for execution on at least one processor, the computer readable program code being configured to be executed by the at least one processor to perform:
- determining a first set of constraints based on anonymity requirements from a privacy model, each record of a dataset having an anonymity constraint of the first set of constraints;
- determining a second set of constraints based on knowledge hiding requirements, each constraint of the second set of constraints corresponds to a respective pattern to be concealed in de-identified data;
- generating a model to determine minimum loss of analytic utility in a dataset for de-identification while satisfying the first set of constraints and the second set of constraints, the generating the model further comprising:
- selectively replacing items in each constraint of the first set of constraints and items in each constraint of the second set of constraints with binary variables used by the constraint satisfaction problem, wherein each of the binary variables indicates either a presence or an absence of a corresponding item in the de-identified data, and
- assigning a value to each of the binary variables such that the first set of constraints and the second set of constraints are satisfied and a sum of the binary variables of the constraint satisfaction problem is maximized;
- applying the model to the dataset to determine changes to the dataset for de-identification that satisfy the first set of constraints and the second set of constraints, the applying the model comprising:
- formulating and solving the constraint satisfaction problem, and
- determining ones of items of the dataset to be changed based on values of the binary variables of the constraint satisfaction problem;
- and
- producing the de-identified data by modifying the dataset in accordance with the determined changes.
Dependencies are inferred from the claim text.