US6092065A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for discovery, clustering and classification of patterns in 1-dimensional event streams
Assignee: International Business Machines Corp
•
Filing: 1998-02-13
•
Granted: 2000-07-18
•
Expires: 2018-02-13
Abstract
Abstract The present invention groups character sequences by identifying a sequence of characters. A set of internal repeats in said sequence of characters is identified by a pattern discovery technique. For at least one internal repeat belonging to the set of internal repeats, it is determined if the internal repeat corresponds to a group of character sequences; If so, first data that identifies the sequence of characters and second data that associates the sequence of characters with the group of character sequences is stored in persistent memory. The pattern discovery mechanism 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.
Inventors
- 👤 Aristidis Floratos
- 👤 Isidore Rigoutsos
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 23:13
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; G06F18/00; G06F18/20; G06F18/23; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/917; Y10S707/953; Y10S707/961; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 58
Claim 1
Independent Claim
191 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for grouping of character sequences, said method steps comprising: identifying a sequence of characters; identifying a set of internal repeats in said sequence of characters by: 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; for at least one internal repeat belonging to said set of internal repeats, determining if said at least one internal repeat corresponds to a group of character sequences; upon determining that said at least one internal repeat corresponds to a group of character sequences, storing in persistent storage first data that identifies said sequence of characters and second data that associates said sequence of characters with said group of character sequences.
Claim 2
Dependent Claim
191 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for grouping of character sequences, said method steps comprising: identifying a sequence of characters; identifying a set of internal repeats in said sequence of characters by: 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; for at least one internal repeat belonging to said set of internal repeats, determining if said at least one internal repeat corresponds to a group of character sequences; upon determining that said at least one internal repeat corresponds to a group of character sequences, storing in persistent storage first data that identifies said sequence of characters and second data that associates said sequence of characters with said group of character sequences.
Claim 3
Dependent Claim
48 words
The program storage device of claim 1, wherein the determining step comprises the steps of: identifying a set of substrings contained in said at least one internal repeat; for at least one substring within said set of substrings, identifying a group associated with said at least one substring.
Claim 4
Dependent Claim
38 words
The program storage device of claim 2, wherein association between a group and a substring is determined by: storing a list of substrings associated with the group; determining whether said substring exactly matches a substring in the list.
Claim 5
Dependent Claim
40 words
The program storage device of claim 2, wherein association between a group and a substring is determined by: storing a list of substrings associated with the group; determining whether said substring substantially overlaps one or more substrings in the list.
Claim 6
Dependent Claim
42 words
The program storage device of claim 1, wherein said set of internal repeats is ranked based upon a predetermined metric to form a ranked list of internal repeats, and wherein said at least one internal repeat is selected from said the list.
Claim 7
Dependent Claim
14 words
The program storage device of claim 1, wherein said character sequences represent protein sequences.
Claim 8
Dependent Claim
14 words
The program storage device of claim 1, wherein said character sequences represent text streams.
Claim 9
Dependent Claim
20 words
The program storage device of claim 1, wherein said character sequences represent one of phonemes and tonemes of continuous speech.
Claim 10
Dependent Claim
15 words
The program storage device of claim 1, wherein said second set of patterns is non-redundant.
Claim 11
Dependent Claim
26 words
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.
Claim 12
Dependent Claim
20 words
The program storage device of claim 1, wherein each pattern within said second set of patterns satisfies a predetermined criterion.
Claim 13
Dependent Claim
25 words
The program storage device of claim 11, wherein said predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.
Claim 14
Dependent Claim
21 words
The program storage device of claim 11, wherein said predetermined criterion comprises one of a minimum length and a maximum length.
Claim 15
Dependent Claim
28 words
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.
Claim 16
Dependent Claim
30 words
The program storage device of claim 1, wherein each template within said proper set of proper templates is defined by data representing a sequence of characters over an alphabet {0,1}.
Claim 17
Dependent Claim
23 words
The program storage device of claim 1, wherein each pattern is associated with a a first field that identifies characters of said pattern.
Claim 18
Dependent Claim
40 words
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.
Claim 19
Dependent Claim
25 words
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.
Claim 20
Dependent Claim
35 words
The program storage device of claim 18, 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.
Claim 21
Dependent Claim
44 words
The program storage device of claim 19, 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.
Claim 22
Dependent Claim
44 words
The program storage device of claim 19, 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.
Claim 23
Dependent Claim
35 words
The program storage device of claim 19, 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.
Claim 24
Dependent Claim
34 words
The program storage device of claim 19, 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.
Claim 25
Dependent Claim
25 words
The program storage device of claim 19, further comprising the step of reporting said third set of patterns to a user via an input/output device.
Claim 26
Dependent Claim
22 words
The program storage device of claim 19, wherein the combining step combines patterns that are convolvable under the operator ⊕ R .
Claim 27
Dependent Claim
32 words
The program storage device of claim 19, further comprising the step of identifying a value L, and wherein the combining step combines patterns that are convolvable under the operator ⊕ L-1 .
Claim 28
Dependent Claim
174 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for grouping of character sequences, said method steps comprising: identifying a sequence of characters; identifying a set of internal repeats in said sequence of characters by: 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; for at least one internal repeat belonging to said set of internal repeats, determining if said at least one internal repeat corresponds to a group of character sequences; upon determining that said at least one internal repeat corresponds to a group of character sequences, storing in persistent storage first data that identifies said sequence of characters and second data that associates said sequence of characters with said group of character sequences.
Claim 29
Dependent Claim
174 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for grouping of character sequences, said method steps comprising: identifying a sequence of characters; identifying a set of internal repeats in said sequence of characters by: 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; for at least one internal repeat belonging to said set of internal repeats, determining if said at least one internal repeat corresponds to a group of character sequences; upon determining that said at least one internal repeat corresponds to a group of character sequences, storing in persistent storage first data that identifies said sequence of characters and second data that associates said sequence of characters with said group of character sequences.
Claim 30
Dependent Claim
48 words
The program storage device of claim 27, wherein the determining step comprises the steps of: identifying a set of substrings contained in said at least one internal repeat; for at least one substring within said set of substrings, identifying a group associated with said at least one substring.
Claim 31
Dependent Claim
38 words
The program storage device of claim 28, wherein association between a group and a substring is determined by: storing a list of substrings associated with the group; determining whether said substring exactly matches a substring in the list.
Claim 32
Dependent Claim
40 words
The program storage device of claim 28, wherein association between a group and a substring is determined by: storing a list of substrings associated with the group; determining whether said substring substantially overlaps one or more substrings in the list.
Claim 33
Dependent Claim
42 words
The program storage device of claim 27, wherein said set of internal repeats is ranked based upon a predetermined metric to form a ranked list of internal repeats, and wherein said at least one internal repeat is selected from said the list.
Claim 34
Dependent Claim
14 words
The program storage device of claim 27, wherein said character sequences represent protein sequences.
Claim 35
Dependent Claim
14 words
The program storage device of claim 27, wherein said character sequences represent text streams.
Claim 36
Dependent Claim
20 words
The program storage device of claim 27, wherein said character sequences represent one of phonemes and tonemes of continuous speech.
Claim 37
Dependent Claim
35 words
The program storage device of claim 27, 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.
Claim 38
Dependent Claim
44 words
The program storage device of claim 35, 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.
Claim 39
Dependent Claim
44 words
The program storage device of claim 35, 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.
Claim 40
Dependent Claim
35 words
The program storage device of claim 35, 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.
Claim 41
Dependent Claim
34 words
The program storage device of claim 35, 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.
Claim 42
Dependent Claim
25 words
The program storage device of claim 35, further comprising the step of reporting said third set of patterns to a user via an input/output device.
Claim 43
Dependent Claim
22 words
The program storage device of claim 27, wherein the combining step combines patterns that are convolvable under the operator ⊕ R .
Claim 44
Dependent Claim
150 words
The program storage device of claim 41, 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.
Claim 45
Dependent Claim
26 words
The program storage device of claim 42, wherein said first predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.
Claim 46
Dependent Claim
63 words
The program storage device of claim 43, 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.
Claim 47
Dependent Claim
22 words
The program storage device of claim 42, wherein said first predetermined criterion comprises one of a minimum length and a maximum length.
Claim 48
Dependent Claim
42 words
The program storage device of claim 45, 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.
Claim 49
Dependent Claim
110 words
The program storage device of claim 42, 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.
Claim 50
Dependent Claim
82 words
The program storage device of claim 42, 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.
Claim 51
Dependent Claim
29 words
The program storage device of claim 47, wherein, for each pattern P' within said third set of patterns, said second predetermined criterion requires that said pattern P' is maximal.
Claim 52
Dependent Claim
30 words
The program storage device of claim 42, wherein, in step iv), said predetermined ordering scheme orders said set Q of patterns such that maximal patterns are generated before non-maximal patterns.
Claim 53
Dependent Claim
23 words
The program storage device of claim 50, wherein said predetermined ordering scheme orders said set Q of patterns according to a prefix relation.
Claim 54
Dependent Claim
27 words
The program storage device of claim 51, wherein said prefix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1≦ pf Q1.
Claim 55
Dependent Claim
23 words
The program storage device of claim 50, wherein said predetermined ordering scheme orders said set Q of patterns according to a suffix relation.
Claim 56
Dependent Claim
27 words
The program storage device of claim 53, wherein said suffix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1≦ sf Q1.
Claim 57
Dependent Claim
52 words
The program storage device of claim 27, 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.
Claim 58
Dependent Claim
19 words
The program storage device of claim 55, wherein each template within said set of templates is a proper template.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-18 | 2004-01-17 | 2004-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-18 | 2008-01-17 | 2008-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-18 | 2012-01-17 | 2012-07-18 | $7700.00 | Window Closed / Lapsed |