Methods for identifying partial periodic patterns and corresponding event subsequences in an event sequence

• US 6,718,317 B1
• Filed: 06/02/2000
• Issued: 04/06/2004
• Est. Priority Date: 06/02/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Wei, Yu, Philip Shi-lung, Yang, Jiong
• Primary Examiner(s): Patel, Ramesh
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/585,757
• Time in Patent Office: 1,404 Days
• Field of Search: 706/50, 706/55, 382/107
• US Class Current: 706/50
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 2218/12 Classification; Matching

Abstract

A method is provided for identifying partial periodic patterns in an event sequence, wherein pattern includes a list of events from the event sequence. At least one subsequence of the event sequence and at least pattern in the at least one subsequence is identified, such that the at least one pattern exceeds a minimum number of repetitions in the at least one subsequence, and a distance between successive repetitions of the at least one pattern in the at least one subsequence does not exceed a predefined distance threshold. At least one of the at least one pattern and the at least one subsequence is stored.

Claims

1. A method for identifying partial periodic patterns in an event sequence, each pattern comprising a list of events from the event sequence, said method comprising the steps of:

identifying at least one subsequence of the event sequence and at least one pattern in the at least one subsequence, such that the at least one pattern exceeds a minimum number of repetitions in the at least one subsequence, and a distance between successive repetitions of the at least one pattern in the at least one subsequence does not exceed a predefined threshold; and

storing at least one of the at least one pattern and the at least one subsequence.

2. The method according to claim 1, wherein each of the events in a given pattern is one of distinct and non-distinct, and each non-distinct event matches any of the distinct events.

3. The method according to claim 1, wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.

4. A method for identifying partial periodic patterns in an event sequence, each pattern comprising a list of events from the event sequence, said method comprising the steps of:

identifying a set CPP of candidate pattern periods and a plurality of sets CE of candidate events, wherein each candidate pattern period in the set CPP corresponds to one of the plurality of sets CE of candidate events;

identifying at least one pattern comprised of the candidate events in one of the plurality of sets CE and having a same period as the corresponding candidate pattern period in the set CPP, and identifying at least one subsequence of the event sequence that comprises the at least one pattern, such that the at least one pattern exceeds a minimum number of repetitions in the at least one subsequence, and a distance between successive repetitions of the at least one pattern in the at least one subsequence does not exceed a predefined distance threshold; and

storing at least one of the at least one pattern and the at least one subsequence.

5. The method according to claim 4, wherein the period of each of the candidate pattern periods in the set CPP is shorter than a pre-specified maximum period length.

6. The method according to claim 4, wherein the at least one subsequence is a longest event subsequence comprising the at least one pattern.

7. The method according to claim 4, wherein said step of identifying the set CPP of candidate pattern periods and the plurality of sets CE of candidate events comprises the steps of:

initializing a plurality of distance counters, each distance counter being associated with one of a plurality of event and period combinations, each combination being comprised of one of the periods from the set CPP and one of the events from the corresponding set CE of candidate events;

updating a value of each of the distance counters to reflect a distance from the associated event to a previous occurrence of the associated event; and

identifying the event and period combinations such that the value of the distance counters associated with each of the identified combinations exceeds the minimum number of repetitions.

8. The method according to claim 4, wherein each of the periods in the plurality of event and period combinations is less than the pre-specified maximum period length.

9. The method according to claim 4, wherein said step of identifying the set CPP of candidate pattern periods and the plurality of sets CE of candidate events comprises the steps of:

identifying singular patterns and subsequences that comprise the singular patterns, wherein each singular pattern has only one position filled by one of the events in the event sequence; and

identifying and validating complex patterns, wherein each complex pattern has more than one position filled by one of the events in the event sequence.

10. The method according to claim 9, further comprising the step of validating singular patterns.

11. The method according to claim 10, wherein said validating step comprises the step of:

for each occurrence of a given singular pattern;

pruning subsequences comprised in a set Z of subsequences, each subsequence in the set Z corresponding to one of the event and period combinations, each period in the corresponding event and period combinations being associated with a given pattern, the given pattern exceeding a minimum number of repetitions in a given subsequence in the set Z, and a distance between successive repetitions of the given pattern in the given subsequence does not exceeding a predefined distance threshold; and

updating subsequences comprised in a set Y based upon ending positions of the subsequences in the set Y, the set Y comprising a list of lists of subsequences, wherein each of the subsequences in the lists comprised in the set Y have a same ending position.

12. The method according to claim 11, wherein said step of pruning the subsequences in the set Z comprises the steps of:

removing all subsequences from the set Z that end more than the predefined distance threshold from a current position of the given singular pattern in a subsequence in the set Z; and

updating a set X, the set X comprising a subsequence in a seq W of subsequences, the subsequence in the set X having more repetitions of the given singular pattern than any of the other subsequences in the set W, each subsequence in the set W being subject to further processing, said updating being performed when the subsequence in the set X has less repetitions than any of the subsequences removed from the set Z.

13. The method according to claim 11, wherein said step of updating the subsequences comprised in the set Y comprises the steps of:

removing all of the subsequences from the set Y that end prior to an immediately preceding position with respect to a currently processed position in the event sequence;

extending the subsequences in the set Y that end exactly at the immediately proceeding position to include a current repetition of the given singular pattern; and

extending the longest subsequence in the set Z by one repetition of the given singular pattern and inserting the longest subsequence into set Y.

14. The method according to claim 13, wherein said step of extending the subsequences in the set Y that end exactly at the immediately preceding position comprises of the step of removing subsequences having less repetitions than a longest subsequence in the set Y, when a number of repetitions of a last segment of the extended subsequences exceeds the predefined threshold.

15. The method according to claim 12, further comprising the step of maintaining at least one data structure for storing the subsequences in the sets Z, Y, X, and W.

16. The method according to claim 15, wherein the at least one data structure is a queue.

17. The method according to claim 15, wherein each of the subsequences in the set Z are arranged in ascending order with respect to ending positions thereof.

18. The method according to claim 15, wherein each of the subsequences in the set Y are arranged in ascending order with respect to ending positions thereof.

19. The method according to claim 9, wherein the events in the event sequence are one of distinct and non-distinct, and said step of identifying and validating the complex patterns comprises the steps of:

identifying a set I of candidate i-patterns from a set J of valid (i−

1)-patterns, each i-pattern comprising i events, each (i−

1)-pattern comprising i−

1 events;

validating the set I of candidate i-patterns; and

repeating said steps of identifying and validating the set I of i-patterns, until one of the set J is empty and all positions of each of the patterns in the set J are filled by distinct events.

20. The method according to claim 19, wherein said step of identifying the set I of candidate i-patterns comprises the steps of:

for a given valid (i−

1)-pattern P in the set W;

identifying an i-pattern P′

by replacing one of the non-distinct events in the given valid (i−

1)-pattern P with one of the distinct events; and

identifying P′

as a candidate i-pattern, when replacing one of the distinct events in P′

by one of the non-distinct events would produce a valid (i−

1)-pattern and no new i-pattern can be identified.

21. The method according to claim 4, wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.

22. A method for identifying partial periodic patterns in an event sequence, each pattern comprising a list of events from the event sequence, said method comprising the steps of:

specifying a minimum number of repetitions of a pattern within a subsequence of the event sequence, and a maximum distance between successive repetitions of the pattern within the subsequence;

identifying patterns of events in the event sequence and subsequences of the event sequence that comprise the patterns; and

storing only the patterns and subsequences such that a stored pattern exceeds the minimum number of repetitions within a stored subsequence and the successive repetitions of the stored pattern within the stored subsequence do not exceed the maximum distance.

23. The method according to claim 22, wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.