Private clustering and statistical queries while analyzing a large database

• US 20060200431A1
• Filed: 03/01/2005
• Published: 09/07/2006
• Est. Priority Date: 03/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dwork, Cynthia, McSherry, Frank David, Nissim Kobliner, Yaacov, Blum, Avrim L.
• Granted Patent: US 7,676,454 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A database has a plurality of entries and a plurality of attributes common to each entry, where each entry corresponds to an individual. A query is received from a querying entity query and is passed to the database, and an answer is received in response. An amount of noise is generated and added to the answer to result in an obscured answer, and the obscured answer is returned to the querying entity. The noise is normally distributed around zero with a particular variance. The variance R may be determined in accordance with R>8 T log²(T/δ)/ε², where T is the permitted number of queries T, δ is the utter failure probability, and ε is the largest admissible increase in confidence. Thus, a level of protection of privacy is provided to each individual represented within the database. Example noise generation techniques, systems, and methods may be used for privacy preservation in such areas as k means, principal component analysis, statistical query learning models, and perceptron algorithms.

Claims

1. A method for preserving privacy of data in a database, comprising:

providing a query to a database;

receiving an answer from the database in response to the query;

generating an amount of noise using a centered normal distribution, defined by the variance R; and

adding the amount of noise to the answer to result in an obscured answer.

2. The method of claim 1, wherein the variance R is responsive to a permitted number of queries.

3. The method of claim 1, wherein the variance R is responsive to a failure probability.

4. The method of claim 1, wherein the variance R is responsive to a largest admissible increase in confidence.

5. The method of claim 1, wherein R is determined in accordance with R>

8 T log²(T/δ

)/ε

², where T is the permitted number of queries T, δ

is the utter failure probability, and ε

is the largest admissible increase in confidence.

6. The method of claim 1, wherein generating the amount of noise comprises generating noise that obscures the answer to a large enough degree to protect privacy, but not to such a large degree as to affect statistical analysis of the database.

7. The method of claim 1, wherein the database comprises a sub-linear queries (SuLQ) database.

8. The method of claim 1, wherein the obscured answer is an arbitrary real number between 0 and 1.

9. The method of claim 1, wherein the query can now operate on arbitrary data comprising at least one of real numbers, strings, and categorical data.

10. The method of claim 1, wherein the obscured answer applies privacy to a real-valued function.

20. The method of claim 1, wherein receiving the answer comprises receiving the answer from a sub-linear queries (SuLQ) database.

11. A method of preserving privacy, comprising:

receiving a portion of an application that references a database;

reformulating the portion of the application as a query; and

running the query pursuant to a sub-linear queries (SuLQ) primitive.

12. The method of claim 11, wherein the application comprises singular value decomposition and optimal projections.

13. The method of claim 11, wherein the application comprises a k means application.

14. The method of claim 11, wherein the application comprises principal component analysis.

15. The method of claim 11, wherein the application comprises a perceptron algorithm.

16. The method of claim 11, wherein the application comprises a statistical query model.

17. A computer readable medium having computer executable instructions stored thereon for performing a method comprising:

receiving an answer in response to the query;

generating an amount of noise using a centered normal distribution, defined by the variance R; and

adding the amount of noise to the answer to result in an obscured answer.

18. The computer readable medium of claim 17, wherein R is determined in accordance with R>

8 T log²(T/δ

)/ε

², where T is the permitted number of queries T, δ

is the utter failure probability, and ε

is the largest admissible increase in confidence.

19. The computer readable medium of claim 17, wherein generating the amount of noise comprises generating noise that obscures the answer to a large enough degree to protect privacy, but not to such a large degree as to affect statistical analysis of the database.