Method and System for Detecting Anomalies in Time Series Data

• US 20110119374A1
• Filed: 10/19/2010
• Published: 05/19/2011
• Est. Priority Date: 10/20/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mui, Lik, Moon, Hui Sok, Van Der Molen, Douglas, Tulsi, Japjit, Ruhl, Jan Matthias
• Granted Patent: US 8,554,699 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation

Abstract

A server system stores time series data for a data source. The time series data comprises a plurality of time-value pairs, each pair including a value associated with an attribute of the data source and a time. For a particular attribute, the server system generates a plurality of forecasting models for characterizing the time-value pairs, each model including an estimated attribute value and an associated error-variance. For a time-value pair, the server system determines a plurality of differences between the value of the time-value pair and respective estimated attribute values of the plurality of forecasting models and tags the time-value pair as an anomaly if the differences for at least a first subset of the forecasting models are greater than the corresponding error variances. In response to a request from a client application, the server system returns at least a subset of the time-value pairs tagged as anomalies.

Claims

1. A computer-implemented method for identifying anomalies in time series data, comprising:

storing in a database time series data for a data source, wherein the time series data comprises a plurality of time-value pairs, each pair including a value of one or more attributes associated with the data source and a time associated with the value;

for a particular attribute, generating a plurality of forecasting models for characterizing the time-value pairs in a respective subset of the time series data, each forecasting model including an estimated attribute value and an associated error-variance;

for a respective time-value pair associated with the particular attribute;

determining a plurality of differences between the value of the time-value pair and respective estimated attribute values of the plurality of forecasting models; and

tagging the time-value pair as an anomaly if the differences for at least a first subset of the forecasting models are greater than the corresponding error variances; and

in response to a request from a client application for analytics information for the data source, reporting to the client application at least a subset of the time-value pairs tagged as anomalies for one or more of the attributes.

2. The computer-implemented method of claim 1, wherein the respective time-value pair for the particular attribute is the latest time-value pair associated with the data source.

3. The computer-implemented method of claim 1, wherein the first subset of the forecasting models comprises one of:

a predetermined number of the forecasting models or a predetermined percentage of the forecasting models.

4. The computer-implemented method of claim 1, further comprising:

for the respective time-value pair and the particular attribute, determining a significance factor such that the respective differences for at least a second subset of the forecasting models are smaller than the corresponding error-variances multiplied by the significance factor, wherein the first subset is within the second subset; and

in response to the request from the client application for the analytics information, the request including a predefined significance threshold for one or more of the attributes, reporting to the client application those time-value pairs tagged as anomalies if their respective significance factors exceed the predefined significance threshold.

5. The computer-implemented method of claim 1, wherein the forecasting models include at least one of a linear regression model and a Holt-Winters exponential smoothing model.

6. The computer-implemented method of claim 1, wherein the forecast models include models computed from 4, 21, and 56 days of time-series data.

7. The computer-implemented method of claim 1, wherein the time series data includes aggregated web analytics data, the computer-implemented method further comprising:

aggregating raw or sessionized web traffic data to generate the aggregated web analytics data for attributes of interest and storing in a database the aggregated web analytics data in addition to the raw or sessionized web traffic data.

8. The computer-implemented method of claim 1, wherein the time series data includes sessionized web analytics data, the computer-implemented method further comprising:

summarizing per session raw web traffic data to generate the sessionized time series data for one or more of the attributes and storing in a database the sessionized time series data in addition to the raw web traffic data.

9. A server system for identifying anomalies in time series data, comprising:

one or more processors for executing programs; and

memory to store data and to store one or more programs to be executed by the one or more processors, the one or more programs including instructions for;

storing in a database time series data for a data source, wherein the time series data comprises a plurality of time-value pairs, each pair including a value of one or more attributes associated with the data source and a time associated with the value;

for a particular attribute, generating a plurality of forecasting models for characterizing the time-value pairs in a respective subset of the time series data, each forecasting model including an estimated attribute value and an associated error-variance;

for a respective time-value pair associated with the particular attribute;

determining a plurality of differences between the value of the time-value pair and respective estimated attribute values of the plurality of forecasting models; and

tagging the time-value pair as an anomaly if the differences for at least a first subset of the forecasting models are greater than the corresponding error variances; and

in response to a request from a client application for analytics information for the data source, reporting to the client application at least a subset of the time-value pairs tagged as anomalies for one or more of the attributes.

10. The server system of claim 9, wherein the respective time-value pair for the particular attribute is the latest time-value pair from the data source.

11. The server system of claim 9, wherein the first subset of the forecasting models comprises one of:

a predetermined number of the forecasting models or a predetermined fraction of the forecasting models.

12. The server system of claim 9, further comprising instructions for:

for the respective time-value pair and the particular attribute, determining a significance factor such that the respective differences for at least a second subset of the forecasting models are smaller than the corresponding error-variances multiplied by the significance factor, wherein the first subset is within the second subset; and

in response to the request from the client application for the analytics information, the request including a predefined significance threshold for one or more of the attributes, reporting to the client application those time-value pairs tagged as anomalies if their respective significance factors exceed the predefined significance threshold.

13. The server system of claim 9, wherein the forecasting models include at least one of a linear regression model and a Holt-Winters exponential smoothing model.

14. The server system of claim 9, wherein the time series data includes aggregated web analytics data, the server system further comprising instructions for:

aggregating raw or sessionized web traffic data to generate the aggregated web analytics data for attributes of interest and storing in a database the aggregated web analytics data in addition to the raw or sessionized web traffic data.

15. The server system of claim 9, wherein the time series data includes sessionized web analytics data, the server system further comprising instructions for summarizing per session raw web traffic data to generate the sessionized time series data for one or more of the attributes and storing in a database the sessionized time series data in addition to the raw web traffic data.

16. A computer readable-storage medium storing one or more programs for execution by one or more processors of a server system for identifying anomalies in time series data, the one or more programs comprising instructions for:

storing in a database time series data for a data source, wherein the time series data comprises a plurality of time-value pairs, each pair including a value of one or more attributes associated with the data source and a time associated with the value;

for a particular attribute, generating a plurality of forecasting models for characterizing the time-value pairs in a respective subset of the time series data, each forecasting model including an estimated attribute value and an associated error-variance;

for a respective time-value pair associated with the particular attribute;

determining a plurality of differences between the value of the time-value pair and respective estimated attribute values of the plurality of forecasting models; and

tagging the time-value pair as an anomaly if the differences for at least a first subset of the forecasting models are greater than the corresponding error variances; and

in response to a request from a client application for analytics information for the data source, reporting to the client application at least a subset of the time-value pairs tagged as anomalies for one or more of the attributes.

17. The computer program product of claim 16, wherein the respective time-value pair for the particular attribute is the latest time-value pair from the data source.

18. The computer program product of claim 16, wherein the first subset of the forecasting models comprises one of:

a predetermined number of the forecasting models or a predetermined fraction of the forecasting models.

19. The computer program product of claim 16, further comprising instructions for:

for the respective time-value pair and the particular attribute, determining a significance factor such that the respective differences for at least a second subset of the forecasting models are smaller than the corresponding error-variances multiplied by the significance factor, wherein the first subset is within the second subset; and

in response to the request from the client application for the analytics information, the request including a predefined significance threshold for one or more of the attributes, reporting to the client application those time-value pairs tagged as anomalies if their respective significance factors exceed the predefined significance threshold.

20. The computer program product of claim 16, wherein the forecasting models include at least one of a linear regression model and a Holt-Winters exponential smoothing model.

21. The computer program product of claim 16, wherein the time series data includes aggregated web analytics data, the computer program product further comprising instructions for:

aggregating raw or sessionized web traffic data to generate the aggregated web analytics data for attributes of interest and storing in a database the aggregated web analytics data in addition to the raw or sessionized web traffic data.

22. The computer program product of claim 16, wherein the time series data includes sessionized web analytics data, the computer program product further comprising instructions for:

summarizing per session raw web traffic data to generate the sessionized time series data for one or more of the attributes and storing in a database the sessionized time series data in addition to the raw web traffic data.

23. A computer system for detecting events of interest in time series data, comprising:

one or more processors for executing programs; and

memory to store data and to store one or more programs to be executed by the one or more processors, the one or more programs including;

a time series data collection module configured to collect time series data at one or more predefined time intervals from a plurality of data sources, wherein the time series data comprises a plurality of time-value pairs, each pair including a value of one attribute associated with the data sources and a time during which the value was collected;

a time series storage module configured to store in the memory the collected time series data such that a time-value pair is added to the stored time series data for a respective collection of time series data without disturbing the stored time series data for the respective collection;

an event detection module configured to determine whether a new time-value pair is an event of interest with reference to its associated collection of time series data, including one or more sub-modules for;

generating a plurality of forecasting models for characterizing different subsets of the collection of time series data, each forecasting model including an estimated attribute value and an associated error-variance;

determining whether the new time-value pair is within a scope defined by the estimated attribute value and the error-variance for each of the plurality of forecasting models; and

tagging the new time-value pair if the new time-value pair is outside the respective scopes for at least a first subset of the forecasting models; and

an event storage module configured to store the tagged time-value pairs such that the tagged time-value pairs are ready to be served in response to a request for events of interest from a client application.

24. The computer system of claim 23, further comprising:

an aggregation module configured to aggregate the collected time series data into aggregated time series data, wherein the aggregated time series data is a summary of raw time series data or sessionized time series data for attributes of interest associated with the data sources, the time series storage module configured for storing the aggregated time series data in addition to the raw time series data or sessionized time series data.

25. The computer system of claim 23, wherein the data sources are web pages stored at web servers and the collected time series data comprises values of metrics and dimensions for the web pages and associated time values during which the values of the metrics and dimensions were collected.

26. The computer system of claim 23, wherein the time series storage module is further configured to quantize and compress the time series data before storing it in the memory.

27. A computer-implemented method for detecting events of interest in time series data, comprising:

collecting time series data at one or more predefined time intervals from a plurality of data sources, wherein the time series data comprises a plurality of time-value pairs, each pair including a value of one attribute associated with the data sources and a time during which the value was collected;

storing in memory the collected time series data such that a time-value pair is added to the stored time series data for a respective collection of time series data without disturbing the stored time series data for the respective collection;

determining whether a new time-value pair is an event of interest with reference to its associated collection of time series data, further including;

generating a plurality of forecasting models characterizing different subsets of the associated collection of time series data, each forecasting model including an estimated attribute value and an associated error-variance;

determining whether the particular new time-value pair is within the associated error-variance for each of the plurality of forecasting models; and

tagging the particular time-value pair as an anomaly when the value of the particular time-value pair is outside the error-variance for at least a first subset of the forecasting models; and

storing the time-value pairs tagged as anomalies such that the stored time-value pairs are ready to be served to a user at a client application in response to a user request for the anomalies.

28. The computer-implemented method of claim 27, further comprising:

generating aggregated time series data from the collected time series data, wherein the aggregate time series summarizes raw time series data or sessionized time series data for particular attributes of interest associated with the data sources, the aggregate data being stored by the time series storage module in addition to stored raw time series data or sessionized time series data.

29. The computer-implemented method of claim 27, wherein the data sources are web pages stored on web servers and the collected time series data comprises values of metrics and dimensions for the web pages and associated time values when the values of the metrics and dimensions were collected.

30. The computer-implemented method of claim 27, wherein the time series storage module is further configured to quantize and compress the time series data before storing it.

31. A computer readable-storage medium storing one or more programs for execution by one or more processors of a server system for identifying anomalies in time series data, the one or more programs comprising instructions for:

collecting time series data at one or more predefined time intervals from a plurality of data sources, wherein the time series data comprises a plurality of time-value pairs, each pair including a value of one attribute associated with the data sources and a time when the value was collected;

storing in a computer memory the collected time series data such that, when a new time-value pair is collected by the time series data collector, the new time-value pair is added to the stored time series data for a respective collection of time series data without disturbing the previously stored time series data for the respective collection;

determining for a particular new time-value pair whether the particular new time-value pair is an anomaly with reference to its associated collection of time series data, including;

generating a plurality of forecasting models characterizing different subsets of the associated collection of time series data, each forecasting model including an estimated attribute value and an associated error-variance;

determining whether the particular new time-value pair is within the associated error-variance for each of the plurality of forecasting models; and

tagging the particular time-value pair as an anomaly when the value of the particular time-value pair is outside the error-variance for at least a first subset of the forecasting models; and

storing the time-value pairs tagged as anomalies such that the stored time-value pairs are ready to be served to a user at a client application in response to a user request for the anomalies.

32. The computer readable-storage medium of claim 31, further comprising instructions for:

generating aggregated time series data from the collected time series data, wherein the aggregate time series summarizes raw time series data or sessionized time series data for particular attributes of interest associated with the data sources, the aggregate data being stored by the time series storage module in addition to stored raw time series data or sessionized time series data.