Systems and methods for discovering partially periodic event patterns

• US 20020107841A1
• Filed: 12/18/2000
• Published: 08/08/2002
• Est. Priority Date: 12/18/2000
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ma, Sheng, Hellerstein, Joseph L.
• Granted Patent: US 6,996,551 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/20 Analysing
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Systems and methods for discovering partially periodic temporal associations, referred to herein as p-patterns, are provided. For example, a p-pattern in computer networks might comprise five repetitions every 30 seconds of a port-down event followed by a port-up event, which in turn is followed by a random gap until the next five repetitions of these events. In one embodiment, the present invention comprises: (i) a normalization step to convert application-oriented event data into an application-independent normalized table; (ii) an algorithm for finding significant period lengths from normalized events (e.g., 30 seconds) using a Chi-squared test; and (iii) an algorithm for finding a partially periodic temporal association (e.g., port-down followed by port-up) given a know period.

Claims

1. A method of discovering one or more partially periodic patterns in event data, the method comprising the steps of:

transforming at least a portion of the event data into event classes such that the event data is non-application-dependent;

determining period lengths for each event class in accordance with occurrences of events in the transformed event data, wherein determination of the period lengths for each event class takes into account a predetermined time tolerance value; and

merging event classes into one or more temporally associated groups in accordance with the period lengths to form the one or more partially periodic patterns.

2. The method of claim 1, wherein the event data transformation step further comprises the step of mapping two or more attributes associated with an event into an event class.

3. The method of claim 2, wherein the mapping step is performed in accordance with a lookup table.

4. The method of claim 1, wherein the event data is in a tabular form with a first number of columns before the transformation step and in a tabular form with a second number of columns after the transformation step, the second number of columns being less than the first number of columns.

5. The method of claim 1, wherein the period length determination step further comprises the steps of:

generating counts of inter-arrival times between adjacent events in the event data;

merging the counts based on the predetermined time tolerance value; and

testing the statistical significance of the merged counts in order to determine the period lengths.

6. The method of claim 5, wherein the statistical significance testing step further comprises the use of a Chi-squared test.

7. The method of claim 1, wherein the event class merging step further comprises the steps of:

filtering events based on the determined period lengths;

setting up a threshold based on the determined period lengths for a level-wise search of the event data so as to find the one or more partially periodic patterns; and

grouping the event classes by period length so as to set an initial candidate set for the level-wise search.

8. Apparatus for discovering one or more partially periodic patterns in event data, the apparatus comprising:

at least one processor operative to;

(i) transform at least a portion of the event data into event classes such that the event data is non-application-dependent;

(ii) determine period lengths for each event class in accordance with occurrences of events in the transformed event data, wherein determination of the period lengths for each event class takes into account a predetermined time tolerance value; and

(iii) merge event classes into one or more temporally associated groups in accordance with the period lengths to form the one or more partially periodic patterns; and

a memory, coupled to the at least one processor, which stores at least one of the event data, the transformed event data, and the one or more partially periodic patterns.

9. The apparatus of claim 8, wherein the event data transformation operation further comprises mapping two or more attributes associated with an event into an event class.

10. The apparatus of claim 9, wherein the mapping operation is performed in accordance with a lookup table.

11. The apparatus of claim 8, wherein the event data is in a tabular form with a first number of columns before the transformation step and in a tabular form with a second number of columns after the transformation step, the second number of columns being less than the first number of columns.

12. The apparatus of claim 8, wherein the period length determination operation further comprises:

(i) generating counts of inter-arrival times between adjacent events in the event data;

(ii) merging the counts based on the predetermined time tolerance value; and

(iii) testing the statistical significance of the merged counts in order to determine the period lengths.

13. The apparatus of claim 12, wherein the statistical significance testing operation further comprises the use of a Chi-squared test.

14. The apparatus of claim 8, wherein the event class merging operation further comprises:

(i) filtering events based on the determined period lengths;

(ii) setting up a threshold based on the determined period lengths for a level-wise search of the event data so as to find the one or more partially periodic patterns; and

(iii) grouping the event classes by period length so as to set an initial candidate set for the level-wise search.

16. The article of claim 15, wherein the event data transformation step further comprises the step of mapping two or more attributes associated with an event into an event class.

17. The article of claim 16, wherein the mapping step is performed in accordance with a lookup table.

18. The article of claim 15, wherein the event data is in a tabular form with a first number of columns before the transformation step and in a tabular form with a second number of columns after the transformation step, the second number of columns being less than the first number of columns.

19. The article of claim 15, wherein the period length determination step further comprises the steps of:

generating counts of inter-arrival times between adjacent events in the event data;

merging the counts based on the predetermined time tolerance value; and

testing the statistical significance of the merged counts in order to determine the period lengths.

20. The article of claim 19, wherein the statistical significance testing step further comprises the use of a Chi-squared test.

21. The article of claim 15, wherein the event class merging step further comprises the steps of:

filtering events based on the determined period lengths;

setting up a threshold based on the determined period lengths for a level-wise search of the event data so as to find the one or more partially periodic patterns; and

grouping the event classes by period length so as to set an initial candidate set for the level-wise search.

15. An article of manufacture for discovering one or more partially periodic patterns in event data, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

transforming at least a portion of the event data into event classes such that the event data is non-application-dependent;

determining period lengths for each event class in accordance with occurrences of events in the transformed event data, wherein determination of the period lengths for each event class takes into account a predetermined time tolerance value; and

merging event classes into one or more temporally associated groups in accordance with the period lengths to form the one or more partially periodic patterns.