Detecting change in data

• US 7,836,111 B1
• Filed: 04/29/2005
• Issued: 11/16/2010
• 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): Do; Chat C
• Application Number:
  US11/119,037
• Time in Patent Office: 2,027 Days
• Field of Search: 708422-426, 708/200, 708/491, 708/671
• US Class Current: 708/200
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

To detect a change in data produced by a system, predicted data values for plural time points are computed. Actual data values for the plural time points are received, and residual values are derived from differences between the predicted data values and actual data values. Based on the computed residual values, a time point at which the change in data occurred is determined.

Claims

1. A method of detecting a change in data produced by a system, comprising:

computing, by a processor, predicted data values for plural time points;

receiving, by the processor, actual data values for the plural time points;

computing, by the processor, residual values derived from differences between the predicted data values and actual data values;

calculating centered residual values that are derived from subtracting an aggregate value of the computed residual values from the computed residual values;

determining, based on the centered residual values, a time point at which the change in data occurred, wherein the determining comprises;

computing cumulative sums of the centered residual values, wherein the cumulative sums are at corresponding plural time points; and

comparing the cumulative sums to at least one threshold to determine whether the change in data has occurred; and

indicating that the change in data has occurred in response to at least one of the cumulative sums crossing the at least one threshold, wherein indicating the change in data comprises indicating a systematic change of data produced by a dynamically changing system that produces data exhibiting at least one of non-linear trends, seasonal effects, and heteroscedasticity.

2. The method of claim 1,

wherein the centered residual values are derived from subtracting an average value of the computed residual values from the computed residual values.

3. The method of claim 1, further comprising:

storing a historical data set of data values; and

generating a predictive model based on the historical data set,

wherein computing the predicted data values is based on the predictive model.

4. The method of claim 3, further comprising:

cleansing the historical data set to remove errors in the historical data set,

wherein generating the predictive model is based on the cleansed historical data set.

5. The method of claim 4, wherein cleansing the historical data set comprises:

determining whether the system that produced the actual data values in the historical data set is available;

in response to determining that the system is available, sending an inquiry to the system regarding a validity of data in the historical data set; and

in response to determining that the system is not available, substituting selected data values in the historical data set with other data values.

6. The method of claim 1, wherein computing predicted data values for the plural time points comprises computing one-step-ahead predicted data values for the plural time points.

7. The method of claim 1, wherein computing predicted data values for the plural time points comprises computing N-step-ahead predicted data values for the plural time points, where N≧

2 .

8. An article comprising at least one machine-readable storage medium containing instructions that when executed cause a processor to:

compute a time series of cumulative sums based on actual data values contained in an input data set, wherein computing the time series of cumulative sums comprises;

computing predicted data values for plural time points;

computing residual values derived from differences between the predicted data values and actual data values;

calculating centered residual values that are derived from subtracting an aggregate value of the computed residual values from the computed residual values, wherein the cumulative sums are cumulative sums of the centered residual values;

compare the cumulative sums in the time series against at least one threshold; and

detect a change of the data values in the input data set in response to at least one of the cumulative sums crossing the at least one threshold, wherein detecting the change of the data values in the input data set comprises detecting a systematic change of data values produced by a dynamically changing system that produces data exhibiting at least one of non-linear trends, seasonal effects, and heteroscedasticity.

9. The article of claim 8, wherein the instructions when executed cause the processor to:

generate a predictive model based on the input data set;

wherein the predicted data values for plural time points are computed using the predictive model.

10. The article of claim 9, wherein the centered residual values are calculated by subtracting an average residual value from corresponding computed residual values.

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

12. The article of claim 8, wherein the instructions when executed cause the processor to:

provide an alert to a user in response to detecting the change.

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

determine if a false alarm has occurred in response to detecting the change.

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

in response to determining that a false alarm has occurred, resetting the at least one threshold to a different value.

15. A method comprising:

generating a predictive model based on an input data set produced by a system;

computing, by a processor, predicted data values for plural time points using the predictive model;

computing, by the processor, residual values based on the predicted data values and actual data values of the input data set;

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

computing, by the processor, a time series of cumulative sums of the centered residual values;

comparing, by the processor, the cumulative sums in the time series against at least one threshold; and

detecting a change of the data values in the input data set in response to at least one of the cumulative sums crossing the at least one threshold, wherein detecting the change of the data values in the input data set comprises detecting a systematic change of data values produced by a dynamically changing system that produces data exhibiting at least one of non-linear trends, seasonal effects, and heteroscedasticity.

16. The method of claim 15, wherein computing the cumulative sums of the centered residual values automatically compensates for a built-in bias of the predictive model.

17. The method of claim 15, further comprising:

determining if a false alarm has occurred in response to detecting the change; and

in response to determining that a false alarm has occurred, resetting the at least one threshold to a different value.

18. A system comprising:

a processor; and

a detection module executable on the processor to detect a change in data by;

calculating a time series of predicted data values;

receiving a time series of actual data values;

calculating residual values based on differences between the predicted data values and actual data values;

calculating centered residual values that are derived from subtracting an aggregate value of the calculated residual values from the calculated residual values;

determining, based on the centered residual values, occurrence of the change in data, wherein the detection module determines occurrence of the change in data by;

computing a time series of cumulative sums of the centered residual values, wherein the computed cumulative sums are at corresponding time points; and

comparing the cumulative sums to at least one threshold to determine whether the change in data has occurred; and

wherein the detection module is executable to indicate that the change in data has occurred in response to at least one of the cumulative sums crossing the at least one threshold, wherein indicating the change in data comprises indicating a systematic change of data produced by a dynamically changing system that produces data exhibiting at least one of non-linear trends, seasonal effects, and heteroscedasticity.

19. The system of claim 18, further comprising:

a storage to store a historical data set of data values,

wherein the detection module is executable to generate a predictive model based on the historical data set, and

wherein the detection module calculates the predicted data values by using the predictive model.

20. A method of detecting a change in an input data set produced by a system, comprising:

computing, by a processor, a time series of cumulative sums based on actual data values contained in the input data set produced by the system, wherein computing the time series of cumulative sums comprises;

computing predicted data values for plural time points;

computing residual values derived from differences between the predicted data values and actual data values;

calculating centered residual values that are derived from subtracting an aggregate value of the computed residual values from the computed residual values, wherein the cumulative sums are cumulative sums of the centered residual values;

comparing, by the processor, the cumulative sums in the time series against at least one threshold; and

detecting a change of the data values in the input data set in response to at least one of the cumulative sums crossing the at least one threshold, wherein detecting the change of the data values in the input data set comprises detecting a systematic change of data values produced by a dynamically changing system that produces data exhibiting at least one of non-linear trends, seasonal effects, and heteroscedasticity.

21. The method of claim 20, further comprising:

generating a predictive model based on the input data set;

wherein the predicted data values for plural time points are computed using the predictive model.

22. The method of claim 21, wherein the centered residual values are calculated by subtracting an average residual value from corresponding computed residual values.