Method and system for detecting anomalies in time series data

• US 8,682,816 B2
• Filed: 09/10/2013
• Issued: 03/25/2014
• Est. Priority Date: 10/20/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ruhl, Jan Matthias, Moon, Hui Sok, Mui, Lik, Tulsi, Japjit, Molen, Douglas Vander
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Smith, Paulinho E
• Application Number:
  US14/023,061
• Publication Number:
  US 20140012901A1
• Time in Patent Office: 196 Days
• Field of Search: None
• US Class Current: 706/12
• 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 significant events in time series data, the method 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, each forecasting model including an estimated attribute value and a corresponding error-variance; and

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

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

determining a significance factor such that each of the plurality of differences for at least a subset of the forecasting models is smaller than the corresponding error-variance multiplied by the significance factor; and

identifying the time-value pair as a significant event in response to a determination that the significance factor exceeds a significance threshold for the particular attribute.

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

3. The method of claim 1, wherein the 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 method of claim 1, further comprising:

receiving a request from a client application for analytics information, wherein the request includes the significance threshold; and

reporting to the client application one or more time-value pairs for which the significance factor exceeds the significance threshold.

5. The 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 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.

7. The 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.

8. A system for identifying significant events in time series data, the system comprising:

a processing circuit comprising one or more processors and one or more memory devices, wherein the processing circuit is configured to;

store 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, generate a plurality of forecasting models for characterizing the time-value pairs, each forecasting model including an estimated attribute value and a corresponding error-variance; and

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

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

determine a significance factor such that each of the plurality of differences for at least a subset of the forecasting models is smaller than the corresponding error-variance multiplied by the significance factor; and

identify the time-value pair as a significant event in response to a determination that the significance factor exceeds a significance threshold for the particular attribute.

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

10. The system of claim 8, wherein the subset of the forecasting models comprises one of:

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

11. The system of claim 8, wherein the processing circuit is further configured to:

receive a request from a client application for analytics information, wherein the request includes the significance threshold; and

report to the client application one or more time-value pairs for which the significance factor exceeds the significance threshold.

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

13. The system of claim 8, wherein the time series data includes aggregated web analytics data, wherein the processing circuit is further configured to:

aggregate raw or sessionized web traffic data to generate the aggregated web analytics data for attributes of interest; and

store in a database the aggregated web analytics data in addition to the raw or sessionized web traffic data.

14. The system of claim 8, wherein the time series data includes sessionized web analytics data, wherein the processing circuit is further configured to:

summarize per session raw web traffic data to generate the sessionized time series data for one or more of the attributes; and

store in a database the sessionized time series data in addition to the raw web traffic data.

15. A non-transitory computer-readable storage medium storing one or more programs for execution by one or more processors of a system for identifying significant events 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, each forecasting model including an estimated attribute value and a corresponding error-variance; and

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

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

determining a significance factor such that each of the plurality of differences for at least a subset of the forecasting models is smaller than the corresponding error-variance multiplied by the significance factor; and

identifying the time-value pair as a significant event in response to a determination that the significance factor exceeds a significance threshold for the particular attribute.

16. The computer-readable storage medium of claim 15, wherein the time-value pair for the particular attribute is the latest time-value pair from the data source.

17. The computer-readable storage medium of claim 15, wherein the subset of the forecasting models comprises one of:

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

18. The computer-readable storage medium of claim 15, further comprising instructions for:

receiving a request from a client application for analytics information, wherein the request includes the significance threshold; and

reporting to the client application one or more time-value pairs for which the significance factor exceeds the significance threshold.

19. The computer-readable storage medium of claim 15, 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.

20. The computer-readable storage medium of claim 15, 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.