Methods and apparatus to construct histogram and wavelet synopses for probabilistic data

• US 8,775,362 B2
• Filed: 02/25/2013
• Issued: 07/08/2014
• Est. Priority Date: 12/12/2008
• Status: Expired due to Fees

• 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, Garofalakis, Minos
• Primary Examiner(s): Wong, Lut
• Assistant Examiner(s): Traktovenko, Ilya
• Application Number:
  US13/776,136
• Publication Number:
  US 20130173525A1
• Time in Patent Office: 498 Days
• Field of Search: 706/52, 706/46, 706/45, 706/62
• US Class Current: 706/52
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/02 using fuzzy logic computing arrangements based on biological models G06N3/00; computing arrangements using knowledge-based models G06N5/00
• CPC Class Codes: G06N 7/06 Simulation on general purpose computers

Abstract

A disclosed example method involves generating a plurality of wavelet coefficient quantities. Each wavelet coefficient quantity is generated based on items represented by probabilistic data. Each wavelet coefficient quantity represents different ones of the items by multiplying corresponding wavelet vectors. The example method also involves determining an error measure associated with each of the plurality of wavelet coefficient quantities, and selecting at least one of the plurality of wavelet coefficient quantities based on its associated error measure. The method also involves displaying parameter information associated with the one of the plurality of wavelet coefficient quantities to represent the probabilistic data.

Claims

1. A method of selecting wavelet coefficients to represent probabilistic data, comprising:

generating an initial wavelet coefficient quantity exceeding a target error value;

iteratively generating different wavelet coefficient quantities until an error measure of a selected one of the different wavelet coefficient quantities is less than or equal to the target error value, the different wavelet coefficient quantities generated based on items represented by probabilistic data having uncertainties as to information of a data transmission that the probabilistic data represents, and each wavelet coefficient quantity representing a different combination of the items;

for the different wavelet coefficient quantities, determining the error measure by determining one corresponding probabilistic expected error for each of the coefficients of the different wavelet coefficient quantities, the probabilistic expected error indicative of an accuracy with which a synopsis represents items associated with a corresponding one of the coefficients;

selecting the selected one of the different wavelet coefficient quantities based on its associated error measure; and

displaying parameter information associated with the selected wavelet coefficient quantity to represent the probabilistic data, the parameter information to reduce data loss associated with at least one of noisy data transmissions or dropped data transmissions.

2. A method as defined in claim 1, further comprising determining the error measure using at least one of a cumulative error metric or a maximum error metric.

3. A method as defined in claim 1, further comprising determining a plurality of representative wavelet coefficient values, the representative wavelet coefficient values corresponding to respective ones of the plurality of wavelet coefficient quantities.

4. A method as defined in claim 3, wherein determining the plurality of representative wavelet coefficient values comprises selecting the plurality of representative wavelet coefficient values from a Haar wavelet matrix to minimize a corresponding error measure between wavelet vectors of the representative wavelet coefficient values and the probabilistic data.

5. A method as defined in claim 1, further comprising generating a first one of the plurality of wavelet coefficient quantities by selecting first coefficients associated with the first one of the plurality of wavelet coefficient quantities, and generating a second one of the plurality of wavelet coefficient quantities by selecting second coefficients associated with the second one of the plurality of wavelet coefficient quantities, wherein at least some of the first coefficients are different than at least some of the second coefficients.

6. A method as defined in claim 1, wherein the probabilistic data is generated by communicating information via a communication network.

7. A method as defined in claim 1, wherein the probabilistic data is representative of radio frequency identification data.

8. A method as defined in claim 1, wherein the probabilistic data is representative of audio information communicated via a communication network.

9. An apparatus to select wavelet coefficients to represent probabilistic data, comprising:

a processor; and

a memory storing machine readable instructions that, when executed by the processor, cause the processor to perform operations comprising;

generating a wavelet coefficient quantity exceeding a target error value;

iteratively generating different wavelet coefficient quantities until an error measure of a selected one of the different wavelet coefficient quantities is less than or equal to the target error value, the different wavelet coefficient quantities generated based on items represented by probabilistic data having uncertainties as to information of a data transmission that the probabilistic data represents, and each wavelet coefficient quantity representing a different combination of the items;

for the different wavelet coefficient quantities, determining the error measure by determining one corresponding probabilistic expected error for each of the coefficients of the different wavelet coefficient quantities, the probabilistic expected error indicative of an accuracy with which a synopsis represents items associated with a corresponding one of the coefficients;

selecting the selected one of the different wavelet coefficient quantities based on its associated error measure; and

displaying parameter information associated with the selected wavelet coefficient quantity to represent the probabilistic data, the parameter information to reduce data loss associated with at least one of noisy data transmissions or dropped data transmissions.

10. An apparatus as defined in claim 9, wherein the operations further comprise determining the error measure using at least one of a cumulative error metric or a maximum error metric.

11. An apparatus as defined in claim 9, wherein the operations further comprise determining a plurality of representative wavelet coefficient values, the representative wavelet coefficient values corresponding to respective ones of the plurality of wavelet coefficient quantities.

12. An apparatus as defined in claim 11, wherein determining the plurality of representative wavelet coefficient values comprises selecting the plurality of representative wavelet coefficient values from a Haar wavelet matrix to minimize a corresponding error measure between wavelet vectors of the representative wavelet coefficient values and the probabilistic data.

13. An apparatus as defined in claim 9, wherein the operations further comprise generating a first one of the plurality of wavelet coefficient quantities by selecting first coefficients associated with the first one of the plurality of wavelet coefficient quantities, and generating a second one of the plurality of wavelet coefficient quantities by selecting second coefficients associated with the second one of the plurality of wavelet coefficient quantities, wherein at least some of the first coefficients are different than at least some of the second coefficients.

14. An apparatus as defined in claim 9, wherein the probabilistic data is generated by reading information from a radio frequency identification tag.

15. An apparatus as defined in claim 9, wherein the probabilistic data is representative of audio information communicated via a communication network.

16. An optical disk comprising instructions which, when executed, cause a machine to perform a method, comprising:

generating a wavelet coefficient quantity exceeding a target error value;

iteratively generating different wavelet coefficient quantities until an error measure of a selected one of the different wavelet coefficient quantities is less than or equal to the target error value, the different wavelet coefficient quantities generated based on items represented by probabilistic data having uncertainties as to information of a data transmission that the probabilistic data represents, and each wavelet coefficient quantity representing a different combination of the items;

for the different wavelet coefficient quantities, determining the error measure by determining one corresponding probabilistic expected error for each of the coefficients of the different wavelet coefficient quantities, the probabilistic expected error indicative of an accuracy with which a synopsis represents items associated with a corresponding one of the coefficients;

selecting the selected one of the different wavelet coefficient quantities based on its associated error measure; and

displaying parameter information associated with the selected wavelet coefficient quantity to represent the probabilistic data, the parameter information to reduce data loss associated with at least one of noisy data transmissions or dropped data transmissions.

17. An optical disk as defined in claim 16, wherein the method further comprises determining the error measure using at least one of a cumulative error metric or a maximum error metric.

18. An optical disk as defined in claim 16, wherein the method further comprises determining a plurality of representative wavelet coefficient values, the representative wavelet coefficient values corresponding to respective ones of the plurality of wavelet coefficient quantities.

19. An optical disk as defined in claim 18, wherein determining the plurality of representative wavelet coefficient values comprises selecting the plurality of representative wavelet coefficient values from a Haar wavelet matrix to minimize a corresponding error measure between wavelet vectors of the representative wavelet coefficient values and the probabilistic data.

20. An optical disk as defined in claim 16, wherein the method further comprises generating a first one of the plurality of wavelet coefficient quantities by selecting first coefficients associated with the first one of the plurality of wavelet coefficient quantities, and generating a second one of the plurality of wavelet coefficient quantities by selecting second coefficients associated with the second one of the plurality of wavelet coefficient quantities, wherein at least some of the first coefficients are different than at least some of the second coefficients.