Method and apparatus for aggregation in uncertain data
View Patent ↗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.
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, wherein a probability distribution function for the uncertain data is unavailable and wherein the uncertainty information for each data point comprises a standard deviation error measure for the data point in the data set;
constructing one or more clusters of data points from the data set, wherein constructing comprises adding a given data point to one of the clusters based on the uncertainty information associated with the given data point;
updating statistics for the cluster to which the given data point is added based on the uncertainty information associated with the given data point; and
storing aggregate statistics for each cluster of the one or more clusters.
2. The method of claim 1 , wherein the step of constructing the one or more clusters uses a partition-based approach.
3. The method of claim 1 , wherein the step of constructing the one or more clusters uses expected distances.
4. The method of claim 3 , wherein the expected distances are computed with the use of first order and second order statistics.
5. The method of claim 1 , wherein the aggregate statistics are maintained along with each cluster.
6. The method of claim 5 , wherein the aggregate statistics are maintained in terms of first order and second order moments of underlying data values of the data set.
7. The method of claim 5 , wherein second order error information is maintained in the aggregate statistics.
8. The method of claim 1 , wherein the data set comprises data from a data stream.
9. 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, wherein a probability distribution function for the uncertain data is unavailable and wherein the uncertainty information for each data point comprises a standard deviation error measure for the data point in the data set;
constructing one or more clusters of data points from the data set, wherein constructing comprises adding a given data point to one of the clusters based on the uncertainty information associated with the given data point;
updating statistics for the cluster to which the given data point is added based on the uncertainty information associated with the given data point; and
storing aggregate statistics for each cluster of the one or more clusters.
10. 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, wherein a probability distribution function for the uncertain data is unavailable and wherein the uncertainty information for each data point comprises a standard deviation error measure for the data point in the data set,
construct one or more clusters of data points from the data set, wherein constructing comprises adding a given data point to one of the clusters based on the uncertainty information associated with the given data point,
update statistics for the cluster to which the given data point is added based on the uncertainty information associated with the given data point, and
store aggregate statistics of the one or more clusters and uncertainty information.
11. The apparatus of claim 10 , wherein constructing the one or more clusters uses a partition-based approach.
12. The apparatus of claim 10 , wherein constructing the one or more clusters uses expected distances.
13. The apparatus of claim 12 , wherein the expected distances are computed with the use of first order and second order statistics.
14. The apparatus of claim 10 , wherein the aggregate statistics are maintained along with each cluster.
15. The apparatus of claim 14 , wherein the aggregate statistics are maintained in terms of first order and second order moments of underlying data values of the data set.
16. The apparatus of claim 14 , wherein second order error information is maintained in the aggregate statistics.
17. The apparatus of claim 10 , wherein the data set comprises data from a data stream.