PRESERVING GEOMETRIC PROPERTIES OF DATASETS WHILE PROTECTING PRIVACY

• US 20140196151A1
• Filed: 01/10/2013
• Published: 07/10/2014
• Est. Priority Date: 01/10/2013
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mishra, Nina, Kenthapadi, Krishnaram, Mironov, IIya
• Application Number:
  US13/737,947
• Publication Number:
  US 20140196151A1
• Time in Patent Office: Days
• US Class Current: 726/26
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

The privacy of a dataset is protected. A private dataset is received that includes multiple rows of multidimensional data. Each row may correspond to a user, and each dimension may be an attribute of the user. A projection matrix is applied to each row to generate a lower dimensional sketch of the row. Noise is added to each of the lower dimensional sketches. The sketches with the added noise may be published together with the projection matrix. The sketches preserve geometric relationships of the original dataset including clustering, distances, and nearest neighbor, and therefore may be useful for data mining purposes while still protecting the privacy of the users.

Claims

1. A method comprising:

receiving a dataset by a computing device;

applying a transformation to the dataset by the computing device to generate a transformed dataset;

adding noise to the transformed dataset by the computing device; and

providing the transformed dataset with the added noise by the computing device.

2. The method of claim 1, wherein the dataset comprises a plurality of rows and the transformation is a projection matrix, and wherein applying the transformation to the dataset by the computing device to generate the transformed dataset comprises applying the projection matrix to each row of the plurality of rows.

3. The method of claim 1, wherein the applied transformation is a secret transformation, or is published.

4. The method of claim 1, further comprising selecting the applied transformation based on one or more values of the dataset, or independently of the one or more values of the dataset.

5. The method of claim 1, wherein the dataset and the transformed dataset each comprise a plurality of rows, and each row of the dataset has a dimension that is greater than a dimension of each row of the transformed dataset.

6. A method comprising:

receiving a dataset by a computing device, wherein the dataset comprises a plurality of rows and each row has a first number of dimensions;

for each row of the dataset, generating a sketch from the row by the computing device, wherein the sketch has a second number of dimensions that is less than the first number of dimensions;

for each sketch, adding noise to the sketch by the computing device; and

providing the generated sketches with the added noise by the computing device.

7. The method of claim 6, wherein the generated sketch is a linear sketch or a non-linear sketch.

8. The method of claim 6, further comprising generating a projection matrix that maps rows in the first number of dimensions to sketches in the second number of dimensions, and wherein generating a sketch from a row comprises applying the projection matrix to the row.

9. The method of claim 8, wherein the projection matrix has an associated I_p-sensitivity, and further comprising determining the noise to add to each sketch based on the associated I_p-sensitivity.

10. The method of claim 6, further comprising generating the added noise based on a privacy guarantee.

11. The method of claim 10, wherein the privacy guarantee comprises one or more of ε

-differential privacy, (ε

,δ

)-differential privacy, anonymity, or a comparison of a posterior probability to a prior probability.

12. The method of claim 6, wherein providing the generated sketches with the added noise comprises publishing the generated sketches with the added noise.

13. The method of claim 6, further comprising:

receiving a selection of a first sketch of the generated sketches with the added noise;

receiving a selection of a second sketch of the generated sketches with the added noise;

receiving a noise parameter associated with the added noise; and

determining a geometric property of the first sketch and the second sketch using the first sketch, the second sketch, and the noise parameter.

14. The method of claim 13, wherein the geometric property is one or more of distances, clusters, or nearest neighbors.

15. The method of claim 6, further comprising receiving a privacy guarantee, and further comprising selecting the second number of dimensions and the added noise based on the privacy guarantee.

16. The method of claim 15, wherein the second number of dimensions and the added noise are selected to provide the privacy guarantee, and to minimize distortions of one or more geometric properties of the dataset.

17. A system comprising:

a dataset provider that generates a dataset, wherein the dataset comprises a plurality of rows and each row has a first number of dimensions; and

a privacy protector that;

receives the generated dataset; and

for each row of the generated dataset,

generates a sketch from the row, wherein the sketch has a second number of dimensions that is less than the first number of dimensions; and

publishes the generated sketches.

18. The system of claim 17, wherein the privacy protector further adds noise to each generated sketch and publishes the generated sketches with the added noise.

19. The system of claim 17, wherein the privacy protector further generates a projection matrix that maps rows in the first number of dimensions to sketches in the second number of dimensions, and the privacy protector generates a sketch from a row by applying the projection matrix to the row.

20. The system of claim 17, further comprising:

a computing device adapted to;

receive the generated sketches;

receive a selection of a first sketch of the generated sketches;

receive a selection of a second sketch of the generated sketches; and

determine a geometric property of the row used to generate the first sketch and the row used to generate the second sketch using the first sketch and the second sketch.