Generating minimality-attack-resistant data

• US 8,631,500 B2
• Filed: 06/29/2010
• Issued: 01/14/2014
• Est. Priority Date: 06/29/2010
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Li, Tiancheng, Srivastava, Divesh
• Primary Examiner(s): ARMOUCHE, HADI S
• Application Number:
  US12/825,466
• Publication Number:
  US 20110321169A1
• Time in Patent Office: 1,295 Days
• Field of Search: None
• US Class Current: 726/26
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

The present disclosure is directed to systems, methods, and computer-readable storage media for generating data and data sets that are resistant to minimality attacks. Data sets having a number of tuples are received, and the tuples are ordered according to an aspect of the tuples. The tuples can be split into groups of tuples, and each of the groups may be analyzed to determine if the group complies with a privacy requirement. Groups that satisfy the privacy requirement may be output as new data sets that are resistant to minimality attacks.

Claims

1. A method comprising:

receiving, at a computer executing an anonymization application, a data set at an anonymization engine, the data set comprising a plurality of tuples;

ordering, by the computer, the tuples in the data set according to an aspect of the tuples;

partitioning, by the computer, the tuples into a plurality of buckets, each of the plurality of buckets comprising a predefined number of the tuples;

selecting, by the computer, a bucket of the plurality of buckets as a group;

determining, by the computer, if the group satisfies a privacy requirement; and

if a determination is made that the group does not satisfy the privacy requirement,

determining if a further bucket of the plurality of buckets is available,

merging the further bucket into the group to form a further group,

determining if the further group satisfies the privacy requirement, and

if a determination is made that the further group satisfies the privacy requirement, outputting a new data set comprising the group and the further group.

2. The method of claim 1, wherein the privacy requirement comprises l-diversity, and the predefined number of tuples comprises l.

3. The method of claim 1, further comprising:

determining if first additional buckets of the plurality of buckets are available; and

outputting the data set, if a determination is made that the first additional buckets are not available.

4. The method of claim 3 further comprising:

merging a further bucket of the additional buckets into the group to obtain a new group, if a determination is made that the additional buckets of the plurality of buckets are available;

determining if the new group satisfies the privacy requirement;

determining if second additional buckets are available, if a determination is made that the new group satisfies the privacy requirement; and

outputting a further new data set comprising the new group, if a determination is made that the second additional buckets are not available.

5. The method of claim 4, further comprising:

identifying a noncompliant group that does not satisfy the privacy requirement; and

removing the noncompliant group before outputting the new data set.

6. The method of claim 1, further comprising:

determining if additional buckets of the plurality buckets are available, if a determination is made that the group satisfies the privacy requirement;

selecting a new group, if a determination is made that the additional buckets are available;

determining if the new group satisfies the privacy requirement; and

taking a further action based upon the determining.

7. The method of claim 1, further comprising:

splitting the data set into a plurality of data set groups;

determining if a selected data set group of the plurality of data set groups satisfies the privacy requirement; and

taking a further action based upon the determining.

8. The method of claim 7, further comprising merging the plurality of data set groups together to obtain the data set and outputting the data set, if a determination is made that the selected data set group does not satisfy the privacy requirement.

9. The method of claim 7, further comprising:

selecting a data set group of the plurality of data set groups;

determining if the data set group of the plurality of data set groups satisfies the privacy requirement; and

splitting the data set group of the plurality of data set groups, if a determination is made that the group of the plurality of groups does satisfy the privacy requirement.

10. The method of claim 1, wherein:

the tuples comprise sensitive data and non-sensitive data, the sensitive data comprising quasi-identifiers and sensitive attributes;

the aspect of the tuples comprises the non-sensitive data; and

the new data set further comprises the quasi-identifiers and the sensitive attributes.

11. The method of claim 1, wherein the data set comprises data collected from a telecommunications network.

12. A system comprising:

a processor; and

a memory that stores computer-executable instructions that, when executed by the processor, cause the processor to perform operations comprising

receiving a data set comprising a plurality of tuples, each of the tuples comprising sensitive data and non-sensitive data;

order the tuples in the data set according to the non-sensitive data;

partitioning, by the computer, the tuples into a plurality of buckets, each of the plurality of buckets comprising a predefined number of the tuples;

selecting a bucket of the plurality of buckets as a group;

determining if the group satisfies a privacy requirement; and

if a determination is made that the group does not satisfy the privacy requirement,

determining if a further bucket of the plurality of buckets is available,

merging the further bucket into the group to form a further group,

determining if the further group satisfies the privacy requirement, and

if a determination is made that the further group satisfies the privacy requirement, outputting a new data set comprising the group and the further group.

13. The system of claim 12, wherein the computer-executable instructions, when executed by the processor, cause the processor to perform operations further comprising:

splitting the data set into a plurality of data set groups;

determining if a selected data set group satisfies the privacy requirement; and

taking an action based upon the determining.

14. A computer-readable storage medium comprising computer-executable instructions that, when executed by a processor, cause the processor to perform operations comprising:

receiving a data set comprising a plurality of tuples, each of the tuples comprising sensitive data and non-sensitive data;

order the tuples in the data set according to the non-sensitive data;

partitioning, by the computer, the tuples into a plurality of buckets, each of the plurality of buckets comprising a predefined number of the tuples;

selecting a bucket of the plurality of buckets as a group;

determining if the group satisfies a privacy requirement; and

if a determination is made that the group does not satisfy the privacy requirement

determining if a further bucket of the plurality of buckets is available,

merging the further bucket into the group to form a further group,

determining if the further group satisfies the privacy requirement, and

if a determination is made that the further group satisfies the privacy requirement, outputting a new data set comprising the group and the further group.

15. The computer-readable storage medium of claim 14, further comprising instructions that, when executed by the processor, cause the processor to perform operations further comprising:

if a determination is made that the group satisfies the privacy requirement;

determining if an additional bucket of the plurality of buckets is available;

outputting the new data set comprising the group, if a determination is made that the additional bucket is not available;

merging the additional bucket into the group, if a determination is made that the additional bucket is available; and

if a determination is made that the group does not satisfy the privacy requirement, outputting the data set.

16. The computer-readable storage medium of claim 14, further comprising instructions that, when executed by the processor, cause the processor to perform operations further comprising:

splitting the data set into a first plurality of data set groups;

selecting a data set group of the first plurality of data set groups;

determining the data set group of the first plurality of data set groups satisfies the privacy requirement;

if a determination is made that the data set group of the first plurality of data set groups does not satisfy the privacy requirement, merging the first plurality of data set groups together to obtain the data set and outputting the data set;

if a determination is made that the data set group of the first plurality of data set groups does satisfy the privacy requirement, recursively splitting the data set group of the first plurality of data set groups into a second plurality of data set groups, and determining if the second plurality of data set groups satisfies the privacy requirement.