Method and apparatus for pattern discovery in 1-dimensional event streams

• US 6,108,666 A
• Filed: 02/13/1998
• Issued: 08/22/2000
• Est. Priority Date: 06/12/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rigoutsos, Isidore, Floratos, Aristidis
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/023,756
• Time in Patent Office: 921 Days
• Field of Search: 707/1-206, 706/12-20
• US Class Current: 1/1
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

The method of the present invention discovers patterns in a sequence of characters in two phases. In a sampling phase, preferably proper templates corresponding to the sequence of characters are generated. Patterns are then generated corresponding to the templates and stored in memory. In a convolution phase, the patterns stored in memory are combined to identify a set of maximal patterns.

Claims

1. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for discovering patterns in at least one sequence of characters, said method steps comprising:

identifying a set of proper templates;

identifying a first set of patterns based on said set of proper templates and said sequence of characters, wherein each pattern within said first set of patterns is contained within said sequence of characters; and

combining patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters.

2. The program storage device of claim 1, wherein said second set of patterns is non-redundant.

3. The program storage device of claim 1, wherein said second set of patterns comprise a set of all non-redundant patterns contained within said sequence of characters.

4. The program storage device of claim 1, wherein each pattern within said second set of patterns satisfies a predetermined criterion.

5. The program storage device of claim 4, wherein said predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.

6. The program storage device of claim 4, wherein said predetermined criterion comprises one of a minimum length and a maximum length.

7. The program storage device of claim 1, further comprising the step of reporting a subset of said second set of patterns to a user via an input/output device.

9. The program storage device of claim 1, wherein each pattern is associated with a first field that identifies characters of said pattern.

10. The program storage device of claim 1, wherein each pattern is associated with a an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of characters of said pattern within said sequence of characters.

11. The program storage device of claim 1, wherein convolvable patterns within said first set of patterns are combined to form said second set of patterns.

12. The program storage device of claim 11, further comprising the step of:

identifying a third set of patterns within said second set of patterns, wherein each pattern within said third set satisfies a predetermined criterion.

13. The program storage device of claim 12, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is greater than a predetermined minimum number of occurrences.

14. The program storage device of claim 12, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is less than a predetermined maximum number of occurrences.

15. The program storage device of claim 12, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern P has a length greater than a predetermined minimum length.

16. The program storage device of claim 12, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern has a length less than a predetermined maximum length.

17. The program storage device of claim 12, further comprising the step of reporting said third set of patterns to a user via an input/output device.

18. The program storage device of claim 12, wherein the combining step combines patterns that are convolvable under the operator ⊕

_R.

19. The program storage device of claim 12, further comprising the step of identifying a value L, and wherein the combining step combines patterns that are convolvable under the operator ⊕

_L-1.

8. The program storage device of claim I, wherein each template within said proper set of proper templates is defined by data representing a sequence of characters over an alphabet {0,1}.

20. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for discovering patterns in a sequence of characters, said method steps comprising:

identifying a first set of patterns, wherein each pattern within said first set of patterns is contained within said sequence of characters; and

combining convolvable patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters.

21. The program storage device of claim 20, further comprising the step of:

identifying a third set of patterns within said second set of patterns, wherein each pattern within said third set satisfies a predetermined criterion.

22. The program storage device of claim 21, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is greater than a predetermined minimum number of occurrences.

23. The program storage device of claim 21, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is less than a predetermined maximum number of occurrences.

24. The program storage device of claim 21, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern P has a length greater than a predetermined minimum length.

25. The program storage device of claim 21, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern has a length less than a predetermined maximum length.

26. The program storage device of claim 21, further comprising the step of reporting said third set of patterns to a user via an input/output device.

27. The program storage device of claim 20, wherein the combining step combines patterns that are convolvable under the operator ⊕

_R.

28. The program storage device of claim 27, further comprising the steps of:

i) storing at least one pattern belonging to said first set of patterns in a stack;

ii) selecting a pattern P stored in a top entry of said stack;

iii) identifying a set Q of patterns, wherein each pattern within said set Q is convolvable with said pattern P under said operator ⊕

_R ;

iv) ordering said set Q of patterns according to a predetermined ordering scheme;

v) traversing through said ordered set of patterns and determining whether a given pattern within said set of ordered patterns satisfies a first predetermined criterion; and

vi) if said given pattern satisfies said first predetermined criterion,

combining said given pattern with said pattern P to form a combined pattern,

storing said combined pattern as a top entry in said stack, and

returning to step ii) to process said combined pattern.

29. The program storage device of claim 28, wherein said first predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.

30. The program storage device of claim 29, wherein each pattern is associated with an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said pattern within said sequence of characters;

and

wherein number of occurrences of a pattern is determined by number of offset identifiers in said offset list associated with said pattern.

31. The program storage device of claim 28, wherein said first predetermined criterion comprises one of a minimum length and a maximum length.

32. The program storage device of claim 31, wherein each pattern is associated with a first field that identifies characters of said pattern;

wherein length of a pattern is determined by calculating number of characters in said first field associated with said pattern.

33. The program storage device of claim 28,

wherein each pattern is associated with a first field that identifies characters of said pattern and is associated with an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said pattern within said sequence of characters;

and

wherein, for a combined pattern corresponding to patterns P1 and Q1, said first field identifies characters of said patterns P1 and Q1 that make up said combined pattern, and said offset list comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said combined pattern within said sequence of characters.

34. The program storage device of claim 33, wherein, for each pattern P'"'"' within said third set of patterns, said second predetermined criterion requires that said pattern P'"'"' is maximal.

35. The program storage device of claim 28, further comprising the steps of:

vi) if the set of ordered patterns is empty or no pattern within the ordered set of patterns satisfies said first predetermined matching criterion,

adding pattern P to said third set of patterns if pattern P satisfies a second predetermined criterion,

removing the entry corresponding to the pattern P from the stack, and

returning to step ii) to process the top entry of the stack until the stack is empty.

36. The program storage device of claim 28, wherein, in step iv), said predetermined ordering scheme orders said set Q of patterns such that maximal patterns are generated before non-maximal patterns.

37. The program storage device of claim 36, wherein said predetermined ordering scheme orders said set Q of patterns according to a prefix relation.

38. The program storage device of claim 37, wherein said prefix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1≦

_pf Q1.

39. The program storage device of claim 36, wherein said predetermined ordering scheme orders said set Q of patterns according to a suffix relation.

40. The program storage device of claim 39, wherein said suffix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1≦

_sf Q1.

41. The program storage device of claim 20, wherein said first set of patterns are identified by:

identifying a set of templates;

identifying a set of patterns based on said set of templates and said sequence of characters, wherein each pattern within said set of patterns is contained within said sequence of characters.

42. The program storage device of claim 41, wherein each template within said set of templates is a proper template.