# US 2014/0196151 A1 · Preserving geometric properties of datasets while protecting privacy > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0196151 A1 - Document ID: US20140196151A1 - Status: Published application - Kind: A1 - Application number: 13/737,947 - Filed: 2013-01-10 - Published: 2014-07-10 - Earliest claimed: 2013-01-10 - Assignees: Microsoft Corporation - Applicants: Microsoft Corporation - Inventors: Nina Mishra; Krishnaram Kenthapadi; IIya Mironov - Web page: https://patentgrep.com/patent/US20140196151A1 ## CPC - G06F 16/258: {Data format conversion from or to a database} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) The method of claim 1, wherein the applied transformation is a secret transformation, or is published. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 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. ### Claim 7 (depends on 6) The method of claim 6, wherein the generated sketch is a linear sketch or a non-linear sketch. ### Claim 8 (depends on 6) 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. ### Claim 9 (depends on 8) The method of claim 8, wherein the projection matrix has an associated Ip-sensitivity, and further comprising determining the noise to add to each sketch based on the associated Ip-sensitivity. ### Claim 10 (depends on 6) The method of claim 6, further comprising generating the added noise based on a privacy guarantee. ### Claim 11 (depends on 10) 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. ### Claim 12 (depends on 6) The method of claim 6, wherein providing the generated sketches with the added noise comprises publishing the generated sketches with the added noise. ### Claim 13 (depends on 6) 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. ### Claim 14 (depends on 13) The method of claim 13, wherein the geometric property is one or more of distances, clusters, or nearest neighbors. ### Claim 15 (depends on 6) 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. ### Claim 16 (depends on 15) 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. ### Claim 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. ### Claim 18 (depends on 17) 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. ### Claim 19 (depends on 17) 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. ### Claim 20 (depends on 17) 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.