Detecting events of interest

• US 7,970,934 B1
• Filed: 07/31/2006
• Issued: 06/28/2011
• Est. Priority Date: 07/31/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Patel, Amit J.
• Primary Examiner(s): NGUYEN, THANH T
• Application Number:
  US11/497,798
• Time in Patent Office: 1,793 Days
• Field of Search: 709/224, 714/5, 725/46, 707/5
• US Class Current: 709/244
• CPC Class Codes: H04L 41/147 for predicting network behaviour

Abstract

Methods, systems, and apparatus, including computer program products, for detecting events of interest. In one aspect, a method includes generating a network traffic model that includes forecasted time series data representative of a frequency of actions related to a network traffic entity, and identifying that an event of interest has occurred based on a comparison of actual time series data related to the network traffic entity with the forecasted time series data.

Claims

1. A computer-implemented method comprising:

logging network traffic at a search engine to generate a log of user interactions with the search engine;

generating a network traffic model for a network traffic entity, the model based on actions in the log that relate to the network traffic entity, the model comprising forecasted time series data representative of a frequency of actions related to the network traffic entity predicted for each of a plurality of time intervals within a forecasted time segment; and

identifying that an event of interest has occurred based on a comparison of (i) actual time series data derived from user interactions related to the network traffic entity, the user interactions occurring in the forecasted time segment with (ii) the forecasted time series data, and wherein generating the network traffic model comprises;

identifying a pattern by comparing sets of historic time series data, each set of historic time series data being associated with a distinct one of a plurality of historic time segments, each historic time segment having respective time intervals corresponding to the time intervals of the forecasted time segment; and

determining the forecasted time series data for the forecasted time segment based on the identified pattern.

2. The method of claim 1, wherein generating the network traffic model comprises:

estimating a confidence interval for each of the plurality of time intervals within the forecasted time segment for the network traffic model, the confidence interval being defined by an upper confidence limit and a lower confidence limit.

3. The method of claim 1, wherein generating the network traffic model comprises:

expressing historic time series data as a best fit curve.

4. The method of claim 1, further comprising:

determining a noise baseline level for the network traffic model based on a difference between historic time series data over a historic time segment with previously forecasted time series data over the same historic time segment.

5. The method of claim 1, wherein:

the actual time series data comprises a set of actual values, each actual value being representative of an actual frequency of actions related to the network traffic entity during a time interval of the forecasted time segment.

6. The method of claim 5, wherein identifying that an event of interest has occurred comprises:

for each time interval within the forecasted time segment, comparing the actual value with the forecasted value corresponding to the time interval to determine whether the actual value exceeds a confidence interval of the forecasted value, and if so, designating the actual value as representative of an occurrence of an event of interest.

7. The method of claim 6, further comprising:

assigning a score to the event of interest based on a temporal displacement of the time interval associated with the actual value that exceeds the confidence interval of the forecasted value with a current time.

8. The method of claim 6, further comprising:

assigning a score to the event of interest based on an amount by which the actual value exceeds the confidence interval of the forecasted value.

9. The method of claim 6, further comprising:

assigning a score to the event of interest based on magnitude of the actual value.

10. The method of claim 1, further comprising:

assigning a score to the event of interest; and

ranking the event of interest against other events of interest based on the score.

11. The method of claim 1, further comprising:

obtaining historic time series data representative of a frequency of actions related to the network traffic entity during a historic time segment that spans a plurality of time intervals.

12. The method of claim 11, wherein obtaining the historic time series data comprises:

collecting historic values, each historic value being representative of an actual frequency of actions during a time interval of the historic time segment.

13. The method of claim 1, further comprising:

prior to identifying that an event of interest has occurred, analyzing the actual time series data to remove outliers indicative of spam.

14. The method of claim 1, further comprising:

generating a report including information representative of the event of interest.

15. The method of claim 14, wherein the information comprises one or more of geographic information, a timestamp, a cookie hash, and a network traffic entity identifier.

16. The method of claim 1, wherein the network traffic entity comprises one of a query term, an electronic media file, or a uniform resource locator.

17. A computer-readable memory device storing instructions which when executed by a data processing apparatus cause the data processing apparatus to perform operations comprising:

logging network traffic at a search engine to generate a log of user interactions with the search engine;

generating a network traffic model for a network traffic entity, the model based on actions in the log that relate to the network traffic entity, the model comprising forecasted time series data representative of a frequency of actions related to the network traffic entity predicted for each of a plurality of time intervals within a forecasted time segment; and

identify that an event of interest has occurred based on a comparison of (i) actual time series data derived from user interactions related to the network traffic entity, the user interactions occurring in the forecasted time segment, with (ii) the forecasted time series data, and wherein identifying that an event of interest has occurred further comprises;

for each time interval within the forecasted time segment, comparing the actual value with the forecasted value corresponding to the time interval to determine whether the actual value exceeds a confidence interval of the forecasted value, and if so, designate the actual value as representative of an occurrence of an event of interest.

18. The computer-readable memory device of claim 17, wherein:

the actual time series data comprises a set of actual values, each actual value being representative of an actual frequency of actions related to the network traffic entity during a time interval of the forecasted time segment.

19. The computer-readable memory device of claim 17, wherein the operations further comprise:

assigning a score to the event of interest; and

ranking the event of interest against other events of interest based on the score.

20. The computer-readable memory device of claim 17, wherein the operations further comprise:

assigning a score to the event of interest based on a temporal displacement of the time interval associated with the actual value that exceeds the confidence interval of the forecasted value with a current time.

21. The computer-readable memory device of claim 17, wherein the operations further comprise:

assigning a score to the event of interest based on an amount by which the actual value exceeds the confidence interval of the forecasted value.

22. The computer-readable memory device of claim 17, wherein the operations further comprise:

assign a score to the event of interest based on magnitude of the actual value.

23. The computer-readable memory device of claim 17, wherein the operations further comprise:

generating a report including information representative of the event of interest.

24. The computer-readable memory device of claim 23, wherein the information comprises one or more of geographic information, a timestamp, a cookie hash, and a network traffic entity identifier.

25. The computer-readable memory device of claim 17, wherein the network traffic entity comprises one of a query term, an electronic media file, or a uniform resource locator.

26. A system comprising:

one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations comprising;

logging network traffic at a search engine to generate a log of user interactions with the search engine;

generating a network traffic model for a network traffic entity, the model based on actions in the log of that relate to the network traffic entity, the model comprising forecasted time series data representative of a frequency of actions related of the network traffic entity predicted for each of a plurality of time intervals within a forecasted time segment; and

identifying that an event of interest has occurred based on a comparison of (i) actual time series data derived from user interactions related to the network traffic entity, the user interactions occurring in the forecasted time segment, with (ii) the forecasted time series data, wherein identifying that an event of interest has occurred comprises;

for each time interval within the forecasted time segment, comparing the actual value with the forecasted value corresponding to the time interval to determine whether the actual value exceeds a confidence interval of the forecasted value, and if so, designating the actual value as representative of an occurrence of an event of interest.

27. The system of claim 26, wherein:

the actual time series data comprises a set of actual values, each actual value being representative of an actual frequency of actions related to the network traffic entity during a time interval of the forecasted time segment.

28. The system of claim 26, wherein the operations further comprise:

assigning a score to the event of interest; and

ranking the event of interest against other events of interest based on the score.

29. The system of claim 26, wherein the operations further comprise:

assigning a score to the event of interest based on a temporal displacement of the time interval associated with the actual value that exceeds the confidence interval of the forecasted value with a current time.

30. The system of claim 26, wherein the operations further comprise:

assigning a score to the event of interest based on an amount by which the actual value exceeds the confidence interval of the forecasted value.

31. The system of claim 26, wherein the operations further comprise:

assigning a score to the event of interest based on magnitude of the actual value.

32. The system of claim 26, wherein the operations further comprise:

generating a report including information representative of the event of interest.

33. The system of claim 32, wherein the information comprises one or more of geographic information, a timestamp, a cookie hash, and a network traffic entity identifier.

34. The system of claim 26, wherein the network traffic entity comprises one of a query term, an electronic media file, or a uniform resource locator.