System and architecture for privacy-preserving data mining

Patent 6931403 Issued on August 16, 2005. Estimated Expiration Date:

January 19, 2020. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Ultrasonic coordinate input apparatus
Patent #: 5637839
Issued on: 06/10/1997
Inventor: Yamaguchi, et al.

Scalable system for K-means clustering of large databases
Patent #: 6012058
Issued on: 01/04/2000
Inventor: Fayyad, et al.

Method for refining the initial conditions for clustering with applications to small and large database clustering
Patent #: 6115708
Issued on: 09/05/2000
Inventor: Fayyad, et al.

Multilevel taxonomy based on features derived from training documents classification using fisher values as discrimination values
Patent #: 6233575
Issued on: 05/15/2001
Inventor: Agrawal, et al.

Scalable system for expectation maximization clustering of large databases
Patent #: 6263337
Issued on: 07/17/2001
Inventor: Fayyad, et al.

Generating a model for raw variables from a model for cooked variables
Patent #: 6405200
Issued on: 06/11/2002
Inventor: Heckerman

Method and system for building a decision-tree classifier from privacy-preserving data Patent #: 6546389
Issued on: 04/08/2003
Inventor: Agrawal, et al.

Inventors

Application

No. 09487191 filed on 01/19/2000

US Classes:

707/10, Distributed or remote access707/6Pattern matching access

Examiners

Primary: Ali, Mohammad M.
Assistant: Fleurantin, Jean Bolte

Attorney, Agent or Firm

Rogitz; John L.

International Class

G06F017/30

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.

Other References

Tendick et al., A Modified Random Perturbation Method for Database Security, vol. 19, No. 1, pp 47-63, Mar. 1994.
Patent Application: “Method and System For Building A Naive Bayes Classifier From Privacy-Preserving Data”, Agrawal et al. U.S. Appl. No. 09/487,697, filed Jan. 19, 2000.
Patent Application: “Method and Sytem For Reconstructing Original Distributions From Radomized Numeric Data”. Agrawal et al. U.S. Appl. No. 09/487,642, filed Jan. 19, 2000.
“Security-Control Methods for Statistical Databases: A Comparative Study”. Adam et al. ACM Computing Surveys. vol. 21, No. 4, pp. 515-556. Dec., 1989.