DIFFERENTIALLY PRIVATE DATA RELEASE

• US 20110208763A1
• Filed: 02/25/2010
• Published: 08/25/2011
• Est. Priority Date: 02/25/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Talwar, Kunal, McSherry, Frank D.
• Granted Patent: US 8,145,682 B2
• Time in Patent Office: Days
• US Class Current: 707/757
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/6263 during internet communication, e.g. revealing personal data from cookies

Abstract

A query log includes a list of queries and a count for each query representing the number of times that the query was received by a search engine. In order to provide differential privacy protection to the queries, noise is generated and added to each count, and queries that have counts that fall below a threshold are removed from the query log. A distribution associated with a function used to generate the noise is referenced to determine a distribution of a number of times that a hypothetical query having a zero count would have its count exceed the threshold after the addition of noise. Random queries of an amount equal to a sample from the distribution of number of times are added to the query log with a count that is greater than the threshold count.

Claims

1. A method comprising:

receiving a list of strings at a computing device through a network, wherein the list of strings comprises a plurality of strings and a count associated with each string;

selecting a threshold count by the computing device;

determining a distribution of a number of times that noise generated by a noise generating function would exceed the threshold count by the computing device;

generating a number of strings according to the determined distribution by the computing device;

generating a count for each generated string by the computing device, wherein the generated count is greater than the threshold count; and

adding the generated strings and generated counts to the list of strings by the computing device.

2. The method of claim 1, further comprising, prior to adding the generated strings and generated counts to the list of strings, for each string in the list of strings:

generating noise using the noise generating function; and

adding the generated noise to the count associated with the string.

3. The method of claim 2, further comprising removing strings from the list of strings with an associated count that is less than the threshold count.

4. The method of claim 1, further comprising providing the list of strings through the network by the computing device.

5. The method of claim 1, wherein the list of strings comprises a query log.

6. The method of claim 1, wherein the noise generating function generates noise according to a Laplacian distribution or a Gaussian distribution.

7. The method of claim 1, further comprising compressing the strings in the list of strings.

8. The method of claim 7, wherein the strings are compressed using Huffman coding.

9. The method of claim 1, wherein the distribution is a binomial distribution.

10. The method of claim 1, wherein each string comprises characters from a set of characters and each string has a maximum length, and further wherein selecting the threshold count comprises selecting the threshold count that is the maximum length multiplied by the natural log of the number of characters from the set of characters.

11. A method comprising:

receiving a list of strings by a computing device, wherein the list of strings comprises a plurality of strings and a count associated with each string and each string further has an associated length;

selecting a first length by the computing device;

determining a first threshold count based on the first length by the computing device;

for each string in the list of strings with an associated length equal to the first length;

generating noise using a noise generating function by the computing device; and

adding the generated noise to the count associated with the string by the computing device;

removing strings from the list of strings of a length equal to the first length with a count that is less than the first threshold count by the computing device;

determining a distribution of a number of times that the generated noise by the noise generating function would exceed the first threshold count by the computing device;

generating a number of strings of length equal to the first length according to the determined distribution by the computing device;

generating a count for each generated string by the computing device, wherein the generated count for each string is greater than the first threshold count; and

adding the generated strings and generated counts to the list of strings by the computing device.

12. The method of claim 11, further comprising:

selecting a second length;

determining a second threshold count based on the second length;

for each string in the list of strings with an associated length equal to the second length;

generating noise using the noise generating function; and

adding the generated noise to the count associated with the string;

removing strings from the list of strings of a length equal to the second length with a count that is less than the second threshold count;

determining a distribution of a number of times that the generated noise by the noise generating function would exceed the second threshold count;

generating a number of strings of a length equal to the second length according to the determined distribution;

generating a count for each generated string, wherein the generated count for each string is greater than the second threshold count; and

adding the generated strings and generated counts to the list of strings.

13. The method of claim 12, further comprising providing the list of strings.

14. The method of claim 11, wherein the list of strings is a query log.

15. The method of claim 11, wherein each string comprises characters from a set of characters, and further wherein selecting the first threshold count comprises selecting a first threshold count that is the first length multiplied by the natural log of the number of characters from the set of characters.

16. The method of claim 11, further comprising compressing the strings in the list of strings.

17. A system comprising:

a search engine that generates a query log, wherein the query log comprises a plurality of queries and a count associated with each query;

a query privacy preservation platform that;

receives the query log;

selects a threshold count;

determines a distribution of a number of times that noise generated by a noise generating function would exceed the threshold count;

generates a number of queries according to the distribution;

generates a count for each generated query, wherein each generated count is greater than the threshold count; and

adds the generated queries and generated counts to the query log.

18. The system of claim 17, wherein the query privacy preservation platform, prior to adding the generated queries and generated counts to the query log, for each query in the query log:

generates noise using the noise generating function; and

adds the generated noise to the count associated with the query.

19. The system of claim 18, wherein the query privacy preservation platform further removes queries from the query log with an associated count that is less than the threshold count.

20. The system of claim 17, wherein the query privacy preservation platform further provides the query log to a computing device through a network.