Method and system for reconstructing original distributions from randomized numeric data

• US 6,687,691 B1
• Filed: 01/19/2000
• Issued: 02/03/2004
• Est. Priority Date: 01/19/2000
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Srikant, Ramakrishnan
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/487,642
• Time in Patent Office: 1,476 Days
• Field of Search: 707/101, 707/6, 707/7, 707/102, 707/100, 707/10, 707/104, 707/103
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method for mining data while preserving a user'"'"'s privacy includes perturbing user-related information at the user'"'"'s computer and sending the perturbed data to a Web site. At the Web site, perturbed data from many users is aggregated, and from the distribution of the perturbed data, the distribution of the original data is reconstructed, although individual records cannot be reconstructed. Based on the reconstructed distribution, a decision tree classification model or a Naive Bayes classification model is developed, with the model then being provided back to the users, who can use the model on their individual data to generate classifications that are then sent back to the Web site such that the Web site can display a page appropriately configured for the user'"'"'s classification. Or, the classification model need not be provided to users, but the Web site can use the model to, e.g., send search results and a ranking model to a user, with the ranking model being used at the user computer to rank the search results based on the user'"'"'s individual classification data.

Claims

1. A computer-implemented method for maintaining the privacy of a user of a user computer, comprising the acts of:

at the user computer, perturbing original data to render perturbed data of original data;

receiving, at a Web server, perturbed data of original data associated with the user computer such that the original data is never sent to the Web server; and

reconstructing an estimate of a distribution of the original data using the perturbed data at the Web server.

2. The method of claim 1, wherein perturbed data is generated from plural original data associated with respective plural user computers.

3. The method of claim 2, wherein at least some of the data is perturbed using a uniform probability distribution.

4. The method of claim 2, wherein at least some of the data is perturbed using a Gaussian probability distribution.

5. The method of claim 2, wherein at least some of the data is perturbed by selectively replacing the data with other values based on a probability.

6. The method of claim 2, wherein the reconstruction act includes iteratively determining a density function.

7. The method of claim 2, wherein the reconstruction act includes:

partitioning the perturbed data into intervals; and

iteratively determining a partition probability using the intervals.

8. The method of claim 1, further comprising using the estimate to generate at least one data mining model.

9. A computer system including at least one program of instructions including structure to undertake method acts comprising:

at a user computer, randomizing at least some original values of at least some numeric attributes to render perturbed values;

sending only the perturbed values to a server computer via the Web; and

at the server computer, reconstructing an estimate of a distribution of the original data using the perturbed data, wherein the server computer cannot access the original values.

10. The system of claim 9, wherein the method acts further comprise processing the perturbed values to generate at least one classification model.

11. The system of claim 10, wherein perturbed values are generated from plural original values associated with respective plural user systems, and wherein the original values cannot be reconstructed from the respective perturbed values.

12. The system of claim 10, wherein at least some of the original values are perturbed using a uniform probability distribution or from a Gaussian probability distribution.

13. The system of claim 10, wherein the method acts further comprise perturbing categorical values of at least some categorical attributes by selectively replacing the categorical values with other values based on a probability.

14. A system storage device including system readable code readable by a server system, comprising:

logic means for randomizing at least some original values of at least some numeric attributes to render perturbed values at a user computer; and

logic means for sending only the perturbed values to a server computer via the Internet, whereby the server computer cannot access the original values but uses the perturbed values to reconstruct an estimate of a distribution of the original data using the perturbed data.

15. The device of claim 14, further comprising logic means for processing the perturbed values to generate at least one classification model.

16. The device of claim 15, wherein perturbed values are generated from plural original values associated with respective plural user devices, and wherein the original values cannot be reconstructed from the respective perturbed values.

17. The device of claim 14, wherein at least some of the original values are perturbed using a uniform probability distribution or from a Gaussian probability distribution.

18. The device of claim 14, further comprising logic means for perturbing categorical values of at least some categorical attributes by selectively replacing the categorical values with other values based on a probability.