Method and Apparatus for Aggregation in Uncertain Data

• US 20090222472A1
• Filed: 02/28/2008
• Published: 09/03/2009
• Est. Priority Date: 02/28/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Granted Patent: US 8,005,839 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

Techniques are disclosed for aggregation in uncertain data in data processing systems. For example, a method of aggregation in an application that involves an uncertain data set includes the following steps. The uncertain data set along with uncertainty information is obtained. One or more clusters of data points are constructed from the data set. Aggregate statistics of the one or more clusters and uncertainty information are stored. The data set may be data from a data stream. It is realized that the use of even modest uncertainty information during an application such as a data mining process is sufficient to greatly improve the quality of the underlying results.

Claims

1. A method of aggregation in an application that involves an uncertain data set, comprising the steps of:

obtaining as input the uncertain data set along with uncertainty information;

constructing one or more clusters of data points from the data set; and

storing aggregate statistics of the one or more clusters and uncertainty information.

2. The method of claim 1, wherein the uncertainty information comprises a variance of the data set.

3. The method of claim 1, wherein the uncertainty information comprises a probability density function of the data set.

4. The method of claim 1, wherein the step of constructing the one or more clusters uses a partition-based approach.

5. The method of claim 1, wherein the step of constructing the one or more clusters uses expected distances.

6. The method of claim 5, wherein the expected distances are computed with the use of first order and second order statistics.

7. The method of claim 1, wherein the aggregate statistics are maintained along with each cluster.

8. The method of claim 7, wherein the aggregate statistics are maintained in terms of first order and second order moments of underlying data values of the data set.

9. The method of claim 7, wherein second order error information is maintained in the aggregate statistics.

10. The method of claim 1, wherein the data set comprises data from a data stream.

11. An article of manufacture for aggregation in an application that involves an uncertain data set, comprising a computer readable storage medium including one or more programs which when executed by a computer perform the steps of:

obtaining as input the uncertain data set along with uncertainty information;

constructing one or more clusters of data points from the data set; and

storing aggregate statistics of the one or more clusters and uncertainty information.

12. Apparatus for aggregation in an application that involves an uncertain data set, comprising:

a memory; and

at least one processor coupled to the memory and operative to obtain as input the uncertain data set along with uncertainty information, construct one or more clusters of data points from the data set, and store aggregate statistics of the one or more clusters and uncertainty information.

13. The apparatus of claim 12, wherein the uncertainty information comprises a variance of the data set.

14. The apparatus of claim 12, wherein the uncertainty information comprises a probability density function of the data set.

15. The apparatus of claim 12, wherein constructing the one or more clusters uses a partition-based approach.

16. The apparatus of claim 12, wherein constructing the one or more clusters uses expected distances.

17. The apparatus of claim 16, wherein the expected distances are computed with the use of first order and second order statistics.

18. The apparatus of claim 12, wherein the aggregate statistics are maintained along with each cluster.

19. The apparatus of claim 18, wherein the aggregate statistics are maintained in terms of first order and second order moments of underlying data values of the data set.

20. The apparatus of claim 18, wherein second order error information is maintained in the aggregate statistics.

21. The apparatus of claim 12, wherein the data set comprises data from a data stream.