Efficient Publication of Sparse Data

• US 20120296898A1
• Filed: 05/19/2011
• Published: 11/22/2012
• 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, Srivastava, Divesh, Procopiuc, Cecilia, Tran, Thanh
• Granted Patent: US 9,251,216 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• 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 computer-implemented method for publishing data, the method comprising computer-implemented operations at least for:

obtaining data at a summarization engine, the data comprising a plurality of entries;

modifying one of the plurality of entries to obtain a resulting value;

determining if the resulting value satisfies a threshold;

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

publishing the data summary.

2. The method of claim 1, wherein the one of the plurality of the entries comprises one of the plurality of entries having a non-zero value.

3. The method of claim 2, further comprising sampling a zero-valued entry from the plurality of entries.

4. The method of claim 3, wherein sampling the zero-valued entry comprises sampling a number of zero-valued entries, the number of zero-valued entries comprising the zero-valued entry, wherein the number is determined according to a statistical distribution, and wherein sampling the zero-valued entry further comprises adding the sampled zero-valued entry to the data summary.

5. The method of claim 4, further comprising adding the zero-valued entry to the data summary.

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

7. 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.

8. The method of claim 1, further comprising not adding the resulting value to the data summary in response to determining that the resulting value does not satisfy the threshold.

9. The method of claim 2, further comprising determining if the plurality of entries comprises a further non-zero entry;

and

selecting the further non-zero entry in response to determining that the plurality of entries comprises the further non-zero entry.

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

11. The method of claim 1, wherein modifying the one of the plurality of entries comprises modifying each non-zero valued entry of the plurality of 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.

12. A computer-implemented method for publishing data, the method comprising computer-implemented operations at least for:

obtaining data at a summarization engine, the data comprising a plurality of entries;

modifying one of the plurality of entries to obtain a resulting value, the one of the plurality of values comprising a non-zero valued entry;

adding the resulting value to a data summary;

sampling a zero-valued entry from the plurality of entries;

adding the zero-valued entry to the data summary; and

publishing the data summary.

13. The method of claim 12, wherein sampling the zero-valued entry comprises sampling a number of zero-valued entries, the number of zero-valued entries comprising the zero-valued entry, and wherein the number is determined according to a statistical distribution.

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

15. The method of claim 13, wherein modifying the one of the plurality of entries comprises sampling the non-zero valued entry and adding the noise to the non-zero valued entry.

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

17. A computer-implemented method for publishing data, the method comprising computer-implemented operations at least for:

obtaining data at a summarization engine, the data comprising a plurality of entries;

assigning a priority value to each of the plurality of entries;

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

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

publishing the data summary.

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.