Performing quality determination of data

• US 7,505,868 B1
• Filed: 04/29/2005
• Issued: 03/17/2009
• Est. Priority Date: 01/31/2005
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Shan, Jerry Z.
• Primary Examiner(s): Lau; Tung S
• Assistant Examiner(s): SUN, XIUQIN
• Application Number:
  US11/117,989
• Time in Patent Office: 1,418 Days
• Field of Search: 702/182, 702/183, 600/345, 700/19
• US Class Current: 702/182
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

To perform data quality assurance, data values from a data source at discrete time points up to time point t are received. At least one estimated value is computed based on at least some of the received data values, and the received data values and estimated data values are applied to an algorithm. A data quality determination of the data value for time point t is performed based on the algorithm.

Claims

1. A method of performing data quality assurance, comprising:

receiving data values from a data source at discrete time points up to and including time point t;

computing at least one estimated value based on at least some of the received data values;

applying the received data values and the at least one estimated value to one of a first algorithm and a second algorithm for detecting changes in the data values, wherein the at least one estimated data value comprises predicted data values for the first algorithm, and the at least one estimated data value comprises a mean of the at least some received data values for the second algorithm, wherein the first algorithm computes cumulative sums based on the received data values and predicted data values, and the second algorithm computes a probability distribution function based on the received data values and the mean;

performing a data quality determination of the data value for time point t based on one of the first and second algorithms; and

providing an indication of the data quality determination for output by an output device.

2. The method of claim 1, wherein performing the data quality determination comprises indicating a data quality problem for the data value at time point t in response to the algorithm detecting a systematic change at time point t.

3. The method of claim 1, wherein the first algorithm is used, and wherein computing the cumulative sums according to the first algorithm comprises:

computing residual values based on the received data values and the predicted data values;

calculating the cumulative sums derived from the residual values; and

comparing the cumulative sums against at least one threshold to detect a data quality problem.

4. The method of claim 3, further comprising:

calculating centered residual values that are derived from subtracting an average value of the computed residual values from the computed residual values,

wherein calculating the cumulative sums comprises calculating cumulative sums of the centered residual values.

5. The method of claim 1, wherein applying the received data values and the predicted data values to the first algorithm comprises applying the received data values and the predicted data values to a cumulative sums algorithm.

6. The method of claim 1, wherein applying the received data values and the mean to the second algorithm comprises applying the received data values and the mean to a generalized likelihood ratio (GLR) algorithm.

7. The method of claim 6, wherein applying the received data values and the mean to the GLR algorithm comprises applying the received data values and the mean to a window-limited GLR algorithm.

8. The method of claim 6, wherein performing the data quality determination using the GLR algorithm comprises calculating a ratio of a likelihood of the received data values based on a model with a change in mean level by the mean of the received data values, to a likelihood of the received data values without the change in the mean level.

9. The method of claim 1, wherein providing the indication for output by the output device comprises providing the indication for output by one of an audio device and a display device.

10. The method of claim 1, wherein the first algorithm is used, the first algorithm comprising a cumulative sums algorithm, and wherein the predicted data values comprise a first set of predicted data values computed using a first predictive model, the method further comprising:

generating a first result based on applying the first set of predicted values to the cumulative sums algorithm;

computing a second set of predicted data values using a second predictive model;

applying the second set of predicted data values to the cumulative sums algorithm for detecting changes in the received data values;

generating a second result based on applying the second set of predicted data values to the cumulative sums algorithm;

determining convergence of the first result and second result;

producing a first output in response to determining that the first result and second result have converged; and

producing a second output in response to determining that the first result and second result have not converged.

11. An article comprising at least one storage medium containing instructions that when executed cause a processor to:

receive data values from a data source at discrete time points;

compute predicted values for a forecast period based on a historical data set and at least some of the received data values;

apply the predicted values to a cumulative sums algorithm for detecting a data quality problem in the received data values;

provide an indication of the data quality problem for output by an output device, wherein detecting the data quality problem in the received data values using the cumulative sums algorithm comprises;

computing residual values based on the received data values and the predicted data values;

calculating aggregate values derived from aggregating the residual values; and

comparing the aggregate values against at least one threshold to detect a change point in the received data values, the change point being one of the discrete time points, and indicating a data quality problem with the data value at the change point,

wherein calculating the aggregate values comprises calculating cumulative sums of the residual values, and wherein comparing the aggregate values comprises comparing the cumulative sums against the at least one threshold;

generate a predictive model based on the historical data set and at least some of the received data values;

wherein computing the predicted data values comprises computing the predicted data values using the predictive model,

wherein detecting the data quality problem in the received data values using the cumulative sums algorithm further comprises;

calculating centered residual values by subtracting an average residual value from corresponding computed residual values,

wherein calculating the cumulative sums comprises calculating the cumulative sums of the centered residual values.

12. The article of claim 11, wherein calculating the cumulative sums of the centered residual values automatically compensates for a built-in bias of the predictive model.

13. An article comprising at least one storage medium containing instructions that when executed cause a processor to:

receive data values from a data source at discrete time points;

compute predicted values for a forecast period based on a historical data set and at least some of the received data values;

applying the predicted values to a cumulative sums algorithm for detecting a data quality problem in the received data values;

provide an indication of the data quality problem for output by an output device,

wherein computing the predicted values comprises computing a first set of predicted values using a first predictive model, and wherein the first set of predicted values is applied to the cumulative sums algorithm for detecting the data quality problem,

wherein the instructions when executed cause the processor to further;

generate a first result based on applying the first set of predicted values to the cumulative sums algorithm;

compute a second set of predicted values using a second predictive model;

apply the second set of predicted values to the cumulative sums algorithm for detecting the data quality problem in the received data values; and

generate a second result based on applying the second set of predicted values to the cumulative sums algorithm.

14. The article of claim 13, wherein the instructions when executed cause the processor to further:

determine convergence of the first result and second result;

produce a first output in response to determining that the first result and second result have converged; and

produce a second output in response to determining that the first result and second result have not converged.

15. The article of claim 13, wherein the instructions when executed cause the processor to:

derive the first predictive model using the historical data set and all of the received data values at the discrete time points; and

derive the second predictive model using the historical data set and less than all of the received data values at the discrete time points.

16. A system comprising:

a processor; and

a detection module executable on the processor to;

receive a time series of data values;

calculate at least one estimated value based on at least some of the received data values;

detect a change in the received data values with one of a first algorithm and a second algorithm that uses the received data values and the at least one estimated value, wherein the at least one estimated data value comprises predicted data values for the first algorithm, and the at least one estimated data value comprises a mean of the at least some received data values for the second algorithm, wherein the first algorithm computes cumulative sums based on the received data values and predicted data values, and the second algorithm computes a probability distribution function based on the received data values and the mean; and

indicate a data quality problem in the received data values based on the change.

17. The system of claim 16, wherein the time series includes time points 1 to t, the data quality problem for the data value at time point t being indicated in response to detecting a systematic change occurring at time point t.

18. The system of claim 16, wherein the detection module is executable to use the first algorithm, and wherein the first algorithm comprises a cumulative sums algorithm.

19. The system of claim 18, wherein the predicted data values are computed using a predictive model based on at least some of the received data values and a historical data set.

20. The system of claim 19, wherein the detection module is executable to further:

calculate residual values based on differences between the predicted data values and received data values;

the change detected by the cumulative sums algorithm using the residual values.

21. The system of claim 16, wherein the detection module is executable to use the second algorithm, and wherein the second algorithm comprises a generalized likelihood ratio algorithm.

22. A system comprising:

means for receiving data values from a data source at discrete time points up to time point t;

means for computing at least one estimated value based on at least some of the received data values;

means for applying the received data values and at least one estimated value to one of a first algorithm and a second algorithm for detecting a systematic change in the data values, wherein the at least one estimated data value comprises predicted data values for the first algorithm, and the at least one estimated data value comprises a mean of the at least some received data values for the second algorithm, wherein the first algorithm computes cumulative sums based on the received data values and predicted data values, and the second algorithm computes a probability distribution function based on the received data values and the mean;

means for performing a data quality determination of the data value for time point t based on one of the first and second algorithms for detecting the systematic change in the data values; and

means for providing an indication of the data quality determination for output by an output device.

23. The system of claim 22, wherein the first algorithm comprises a cumulative sums algorithm and the second algorithm comprises a generalized likelihood ratio algorithm.

24. A method comprising:

storing a historical data set;

receiving input data values at discrete time points;

calculating predicted data values based on the historical data set and at least some of the received input data values;

computing residual values calculated from differences between the predicted data values and received data values;

determining a data quality problem in a data value at one of the discrete time points with a cumulative sums algorithm that uses the residual values; and

providing an indication of the data quality problem for output by an output device,

wherein the predicted data values comprise a first set of predicted data values computed using a first predictive model, the method further comprising;

generating a first result based on applying the first set of predicted values to the cumulative sums algorithm;

computing a second set of predicted data values using a second predictive model;

applying the second set of predicted data values to the cumulative sums algorithm for determining the data quality problem;

generating a second result based on applying the second set of predicted data values to the cumulative sums algorithm;

determining convergence of the first result and second result;

producing a first output in response to determining that the first result and second result have converged; and

producing a second output in response to determining that the first result and second result have not converged.