METHOD, APPARATUS AND COMPUTER PROGRAM PRODUCT FOR PRESERVING PRIVACY IN DATA MINING

• US 20090049069A1
• Filed: 08/09/2007
• Published: 02/19/2009
• Est. Priority Date: 08/09/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip S., Aggarwal, Charu
• Granted Patent: US 7,904,471 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: H04L 63/0407 wherein the identity of one or more communicating identities is hidden cryptographic mechanisms or cryptographic arrangements for anonymous credentials or for identity based cryptographic systems H04L9/00

Abstract

Privacy in data mining of sparse high dimensional data records is preserved by transforming the data records into anonymized data records. This transformation involves creating a sketch-based private representation of each data record, each data record containing only a small number of non-zero attribute value in relation to the high dimensionality of the data records.

Claims

1. A method for preserving privacy in mining of sparse high dimensional data records, comprising the following steps:

receiving the data records having high dimensionality; and

transforming the data records into anonymized data records for use in data mining by creating a sketch-based private representation of each data record, wherein each data record contains only a small number of non-zero attribute values in relation to the high dimensionality of the data records

2. The method of claim 1, wherein each private representation of a data record is created based on an absolute variance of each attribute value.

3. The method of claim 1, wherein each private representation of a data record is created on the basis of a variance of a dot product to nearest neighbors of the record.

4. The method of claim 2, wherein a number of sketch components used in creating each sketch-based private representation is determined so that a variance of a reconstructed attribute satisfies user-parameter delta.

5. The method of claim 3, wherein a number of sketch components used in creating each sketch-based private representation is determined so that a variance of a reconstructed dot product is greater than the absolute value of the dot product.

6. The method of claim 5, wherein the data is transformed into anonymized data records by iteratively processing the data in sorted order repeatedly and constructing sketch representations.

7. The method of claim 1, wherein the sparse high dimensional data includes at least one of text data and binary transaction data.

8. An apparatus for preserving privacy in mining of sparse high dimensional data records, the apparatus comprising:

an input for receiving the data records having high dimensionality; and

a processor for transforming the data records into anonymized data records for use in data mining by creating a sketch-based private representation of each data record, wherein each data record contains only a small number of non-zero attribute values it relation to the high dimensionality of the data records.

9. The apparatus of claim 8, wherein each private representation is created based on an absolute variance of each attribute value.

10. The apparatus of claim 8, wherein each private representation is created on the basis of a variance of a dot product to nearest neighbors of the record.

11. The apparatus of claim 9, wherein a number of sketch components used in creating each sketch-based private representation is determined so that a variance of a reconstructed attribute satisfies user-parameter delta.

12. The apparatus of claim 10, wherein a number of sketch components used in creating each the sketch-based private representation is determined so that a variance of a reconstructed dot product is greater than the absolute value of the dot product.

13. The apparatus of claim 12, wherein the data is transformed into anonymized data records by iteratively processing the data in sorted order repeatedly and constructing sketch representations.

14. The apparatus of claim 8, wherein the sparse high dimensional data includes at least one of text data and binary transaction data.

15. A computer program product for preserving privacy in mining of sparse high dimensional data records, comprising a computer usable medium having a computer readable program, wherein the computer readable program, when executed on a computer, causes the computer to:

receive the data records having high dimensionality; and

transform the data records having high dimensionality into anonymized data records for use in data mining by creating a sketch-based private representation of each data record, wherein each data record contains only a small number of non-zero attribute values in relation to the high dimensionality of the data records.

16. The computer program product of claim 15, wherein each private representation is created based on an absolute variance of each attribute value.

17. The computer program product of claim 15, wherein each private representation is created on the basis of a variance of a dot product to nearest neighbors of the record.

18. The computer program product of claim 16, wherein a number of sketch components used in creating each sketch-based private representation is determined so that a variance of a reconstructed attribute satisfies user-parameter delta.

19. The computer program product of claim 17, wherein a number of sketch components used in creating each sketch-based private representation is determined so that a variance, of a reconstructed dot product is greater than the absolute value of the dot product.

20. The computer program product of claim 19, wherein the data is transformed into anonymized data records by iteratively processing the data in sorted order repeatedly and constructing sketch representations.