Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-01-19
2004-02-03
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06687691
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to mining data from Internet users while preserving the privacy of the users.
2. Description of the Related Art
The explosive progress in computer networking, data storage, and processor speed has led to the creation of very large data bases that record enormous amounts of transactional information, including Web-based transactional information. Data mining techniques can then be used to discover valuable, non-obvious information from large databases.
Not surprisingly, many Web users do not wish to have every detail of every transaction recorded. Instead, many Web users prefer to maintain considerable privacy. Accordingly, a Web user might choose not to give certain information during a transaction, such as income, age, number of children, and so on.
It happens, however, that data mining of Web user information is not only useful to, e.g., marketing companies, but it is also useful in better serving Web users. For instance, data mining might reveal that people of a certain age in a certain income bracket might prefer particular types of vehicles, and generally not prefer other types. Consequently, by knowing the age and income bracket of a particular user, an automobile sales Web page can be presented that lists the likely vehicles of choice to the user, before other types of vehicles, thereby making the shopping experience more relevant and efficient for the user. Indeed, with the above in mind it will be appreciated that data mining makes possible the filtering of data to weed out unwanted information, as well as improving search results with less effort. Nonetheless, data mining used to improve Web service to a user requires information that the user might not want to share.
As recognized herein, the primary task of data mining is the development of models about aggregated data. Accordingly, the present invention understands that it is possible to develop accurate models without access to precise information in individual data records. Surveys of Web users indicate that the majority of users, while expressing concerns about privacy, would willingly divulge useful information about themselves if privacy measures were implemented, thereby facilitating the gathering of data and mining of useful information. The present invention has carefully considered the above considerations and has addressed the noted problems.
SUMMARY OF THE INVENTION
The invention is a general purpose computer programmed according to the inventive steps herein to mine data from users of the Internet while preserving their privacy. The invention can also be embodied as an article of manufacture—a machine component—that is used by a digital processing apparatus and which tangibly embodies a program of instructions that are executable by the digital processing apparatus to undertake the present invention. This invention is realized in a critical machine component that causes a digital processing apparatus to perform the inventive method steps herein. The invention is also a computer-implemented method for undertaking the acts disclosed below.
Accordingly, a computer-implemented method is disclosed for receiving data from at least one user computer via the Internet while maintaining the privacy of a user of the computer. The method includes perturbing original data associated with the user computer to render perturbed data, and then reconstructing an estimate of a distribution of the original data using the perturbed data. If desired, the estimate can be used to generate at least one classification model, or to simply gain an understanding of the profile of the users, or for clustering purposes.
Preferably, perturbed data is generated from plural original data associated with respective plural user computers. At least some of the data can be perturbed using a uniform probability distribution or using a Gaussian probability distribution. Furthermore, at least some of the data is perturbed by selectively replacing the data with other values based on a probability.
As set forth in detail below, the reconstruction act includes iteratively determining a density function. The particularly preferred reconstructing act includes partitioning the perturbed data into intervals, and iteratively determining a partition probability using the intervals.
In another aspect, a computer system includes a program of instructions that in turn includes structure to undertake system acts which include, at a user computer, randomizing at least some original values of at least some numeric attributes to render perturbed values. The program also sends the perturbed values to a server computer, and, at the server computer, an estimate of a distribution of the original data is reconstructed using the perturbed data.
In still another aspect, a system storage device includes system readable code that is readable by a server system for generating at least one classification model based on original data values stored at plural user computers without knowing the original values. The device includes logic means for randomizing at least some original values of at least some numeric attributes to render perturbed values, and logic means for sending the perturbed values to a server computer. Also, logic means are available to the server computer for reconstructing an estimate of a distribution of the original data using the perturbed data.
REFERENCES:
patent: 5787274 (1998-07-01), Agrawal et al.
patent: 5799311 (1998-08-01), Agrawal et al.
patent: 5870735 (1999-02-01), Agrawal et al.
patent: 6055510 (2000-04-01), Henrick et al.
patent: 6115708 (2000-09-01), Fayyad et al.
patent: 6138115 (2000-10-01), Agrawal et al.
patent: 6230151 (2001-05-01), Agrawal et al.
patent: 6247016 (2001-06-01), Rastogi et al.
patent: 6405200 (2002-06-01), Heckerman
patent: 6546389 (2003-04-01), Agrawal et al.
Adam et al, “Security-control methods for statistical databases: A comparative study”, ACM Computing Surveys, vol.21, No.4, pp. 516-556, Dec. 1989.*
Tendick et al., “A modified random perturbation method for database security”, ACM, vol.19, No.1, PP. 48-63, Mar. 1994.*
Muralidhar et al., Security of Random data perturbation methods, ACM, vol.24, No.4, pp. 487-493, Dec. 1999.*
Traub et al., “The statistical security of a Statistical database”, ACM, vol.9, No.4, pp. 672-679, Dec. 1984.*
Palley et al., “The use of regression methodology for the compromise of confidential information in statistical databases”, ACM, vol.12, No.4, pp.593-608, Dec. 1987.
Agrawal Rakesh
Srikant Ramakrishnan
Corrielus Jean M.
International Business Machines - Corporation
Rogitz John L.
LandOfFree
Method and system for reconstructing original distributions... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for reconstructing original distributions..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for reconstructing original distributions... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3353894