Efficient publication of sparse data

• US 9,251,216 B2
• Filed: 05/19/2011
• Issued: 02/02/2016
• Est. Priority Date: 05/19/2011
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Procopiuc, Cecilia, Srivastava, Divesh, Tran, Thanh
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/111,154
• Publication Number:
  US 20120296898A1
• Time in Patent Office: 1,720 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

The present disclosure is directed to systems, methods, and computer-readable storage media for publishing data. A data summary summarizing the data can be generated and published according to several publishing schemes. In some embodiments, non-zero entries are selected and modified and zero entries are sampled according to one or more distribution functions. The sampled and modified values are added to a data summary, or a sample of the sampled and modified values are added to the data summary. The data summary is published, released, used, or otherwise output. In other embodiments, priority values are assigned to each value associated with the data, and a number of entries with the highest values are selected and added to the data summary.

Claims

1. A method comprising:

obtaining, at a computer executing a summarization engine, sparse data comprising a plurality of entries, wherein a majority of the plurality of entries comprise zero-valued entries, and wherein a minority of the plurality of entries comprise non-zero valued entries;

modifying, by the computer, one of the non-zero valued entries to obtain a resulting value;

determining, by the computer, that the resulting value satisfies a threshold;

in response to determining that the resulting value satisfies the threshold, adding, by the computer, the resulting value to a data summary;

sampling, by the computer, one of the zero-valued entries;

adding, by the computer, the one of the zero-valued entries to the data summary; and

publishing, by the computer, the data summary, wherein the data summary comprises an anonymized summary of the sparse data.

2. The method of claim 1, wherein sampling the one of the zero-valued entries comprises sampling a number of zero-valued entries, wherein the number is determined according to a statistical distribution.

3. The method of claim 1, wherein modifying the one of the plurality of entries comprises adding noise to the one of the plurality of entries.

4. The method of claim 1, wherein modifying the one of the plurality of entries comprises adding a value of zero to the one of the plurality of entries.

5. The method of claim 1, further comprising;

in response to determining that the resulting value does not satisfy the threshold, not adding the resulting value to the data summary.

6. The method of claim 1, further comprising:

selecting a second of the non-zero valued entries;

modifying the second of the non-zero valued entries to obtain a second resulting value; and

adding the second resulting value to the data summary.

7. The method of claim 1, wherein the data summary comprises a data summary that is differentially private.

8. The method of claim 1, wherein modifying the one of the non-zero valued entries comprises modifying each of the non-zero valued entries to obtain a plurality of resulting values, and wherein adding the resulting value to the data summary comprises adding each of the plurality of resulting values that satisfies the threshold to the data summary.

9. The method of claim 1, wherein over ninety-five percent of the plurality of entries comprise the zero-valued entries.

10. The method of claim 1, wherein modifying the one of the non-zero valued entries comprises adding geometric noise to the one of the non-zero valued entries.

11. A method comprising:

obtaining, by a computer executing a summarization engine, sparse data comprising a plurality of entries, wherein over half of the plurality of entries comprise zero-valued entries, and wherein less than half of the plurality of entries comprise non-zero valued entries;

modifying, by the computer, one of the non-zero valued entries to obtain a resulting value;

adding, by the computer, the resulting value to a data summary;

sampling, by the computer, one of the zero-valued entries;

adding, by the computer, the one of the zero-valued entries to the data summary; and

publishing, by the computer, the data summary.

12. The method of claim 11, further comprising sampling a number of the zero-valued entries comprising the one of the zero-valued entries, wherein the number is determined according to a statistical distribution.

13. The method of claim 12, wherein modifying the one of the non-zero valued entries comprises drawing a sample from non-zero valued entries and adding noise to the sample from the non-zero valued entries.

14. The method of claim 11, wherein modifying the one of the non-zero valued entries comprises adding noise to the one of the non-zero valued entries.

15. The method of claim 11, wherein the data summary comprises a data summary that is differentially private.

16. The method of claim 11, wherein modifying the one of the non-zero valued entries comprises adding geometric noise to the one of the non-zero valued entries.

17. A method comprising:

obtaining, by a computer executing a summarization engine, sparse data comprising a plurality of entries, wherein a majority of the plurality of entries comprise zero-valued entries, and wherein a minority of the plurality of entries comprise non-zero valued entries;

assigning, by the computer, a priority value to each of the plurality of entries;

drawing, by the computer, a sample from the plurality of entries, the sample comprising a plurality of sampled entries;

adding, by the computer, the plurality of sampled entries to a data summary; and

publishing, by the computer, the data summary, wherein the data summary comprises an anonymized summary of the sparse data.

18. The method of claim 17, further comprising identifying a sample size, wherein a number of the plurality of sampled entries is equal to the sample size.

19. The method of claim 18, wherein drawing the sample comprises selecting the plurality of entries by recursively removing from the plurality of entries, and adding to the data summary, an entry having a highest value.

20. The method of claim 17, wherein the data summary comprises a data summary that is differentially private.