Discovery of Frequent Episodes in Event Sequences.
Sequences of events describing the behavior and actions of users or systems can be collected in several domains. An episode is a collection of events that occur relatively close to each other in a given partial order. We consider the problem of discovering frequently occurring episodes in a sequence. Once such episodes are known, one can produce rules for describing or predicting the behavior of the sequence. We give efficient algorithms for the discovery of all frequent episodes from a given class of episodes, and present detailed experimental results. The methods are in use in telecommunication alarm management.
Introduction
Most data mining and machine learning techniques are adapted towards the
analysis of unordered collections of data. However, there are important application
areas where the data to be analyzed consists of a sequence of events.
Examples of such data are alarms in a telecommunication network, user interface
actions, crimes committed by a person, occurrences of recurrent ill-
nesses, etc. Recently, interest in knowledge discovery from sequential data
has increased: see, e.g., [5, 8, 17, 19, 24].
Abstractly, such data can be viewed as a sequence of events, where each
event has an associated time of occurrence. An example of an event sequence
is represented in Figure 1. Here A; B;C;D;E; and F are event types, e.g.,
dioeerent types of alarms from a telecommunication network, or dioeerent types
of user actions, and they have been marked on a time line.
One basic problem in analyzing such a sequence is to -nd frequent epis-
odes, i.e., collections of events occurring frequently together. For example,
in the sequence of Figure 1, the episode iE is followed by Fj occurs several
times, even when the sequence is viewed through a narrow window. Epis-
odes, in general, are partially ordered sets of events. From the sequence in
the -gure one can make, for instance, the observation that whenever A and
occur (in either order), C occurs soon.
When discovering episodes in a telecommunication network alarm log,
the goal is to -nd relationships between alarms. Such relationships can then
be used in an on-line analysis of the incoming alarm stream, e.g, to better
explain the problems that cause alarms, to suppress redundant alarms, and
to predict severe faults.
In this paper we consider the following problem. Given a class of episodes
and an input sequence of events, -nd all episodes that occur frequently
in the event sequence. We describe the framework and formalize the know-
time
EDF A BCEF C D BAD C EFC BEAECF A D

Figure

1: A sequence of events.
ledge discovery task in Section 2. Algorithms for discovering all frequent
episodes are given in Section 3. Thery are based on the idea of -rst -nding
small frequent episodes, and then progressively looking for larger frequent
episodes. Additionally, the algorithms use some simple pattern matching
ideas to speed up the recognition of occurrences of single episodes. Section 4
outlines an alternative way of approaching the problem, based on locating
minimal occurrences of episodes. Experimental results using both approaches
and with various data sets are presented in Section 5. We discuss extensions
and review related work in Section 6. Section 7 is a short conclusion.
2 Event sequences and episodes
Our overall goal is to analyze sequences of events, and to discover recurrent
combinations of events, which we call frequent episodes. We -rst formulate
the concept of event sequence, and then look at episodes in more detail.
2.1 Event sequences
We consider the input as a sequence of events, where each event has an
associated time of occurrence. Given a set E of event types, an event is a
is an event type and t is an integer, the (occurrence)
time of the event. The event type can actually contain several attributes; for
simplicity we consider here the event type as a single value.
An event sequence s on E is a triple (s; T
EDF A BCEF C D BAD C EFC BEAECF A D

Figure

2: The example event sequence and two windows of width 5.
is an ordered sequence of events such that A i 2 E for all
are integers, T s is
called the starting time and T e the ending time, and T s -
Example 1 Figure 2 presents graphically the event sequence
where
Observations of the event sequence have been made from time 29 to just
before time 68. For each event that occurred in the time interval [29; 68), the
event type and the time of occurrence have been recorded.
In the analysis of sequences we are interested in -nding all frequent episodes
from a class of episodes. To be considered interesting, the events of
an episode must occur close enough in time. The user de-nes how close is
close enough by giving the width of the time window within which the episode
must occur. We de-ne a window as a slice of an event sequence, and
we then consider an event sequence as a sequence of partially overlapping
windows. In addition to the width of the window, the user speci-es in how
many windows an episode has to occur to be considered frequent.
Formally, a window on event sequence is an event sequence
consists of those pairs (A; t)
from s where t s - . The time span t e \Gamma t s is called the width of the
window w, and it is denoted width(w). Given an event sequence s and an
integer win, we denote by W(s; win) the set of all windows w on s such that
By the de-nition the -rst and last windows on a sequence extend outside
the sequence, so that the -rst window contains only the -rst time point of
the sequence, and the last window contains only the last time point. With
this de-nition an event close to either end of a sequence is observed in equally
many windows to an event in the middle of the sequence. Given an event
sequence window width win, the number of windows in
W(s; win) is
Example 2 Figure 2 shows two windows of width 5 on the sequence s of
the previous example. A window starting at time 35 is shown in solid line,
and the immediately following window, starting at time 36, is depicted with
a dashed line. The window starting at time 35 is
Note that the event (F; 40) that occurred at the ending time is not in the
window. The window starting at 36 is similar to this one; the dioeerence is
that the -rst event (A; 35) is missing and there is a new event (F; 40) at the
end.
The set of the 43 partially overlapping windows of width 5 constitutes
W(s; 5); the -rst window is (;; 25; 30), and the last is (h(D;
Event (D; 67) occurs in 5 windows of width 5, as does, e.g., event (C; 50).
2.2 Episodes
Informally, an episode is a partially ordered collection of events occurring
together. Episodes can be described as directed acyclic graphs. Consider,
for instance, episodes ff, fi, and fl in Figure 3. Episode ff is a serial episode:
it occurs in a sequence only if there are events of types E and F that occur
ff
A
A

Figure

3: Episodes ff; fi, and fl.
in this order in the sequence. In the sequence there can be other events
occurring between these two. The alarm sequence, for instance, is merged
from several sources, and therefore it is useful that episodes are insensitive
to intervening events. Episode fi is a parallel episode: no constraints on the
relative order of A and B are given. Episode fl is an example of non-serial
and non-parallel episode: it occurs in a sequence if there are occurrences of
A and B and these precede an occurrence of C; no constraints on the relative
order of A and B are given. We mostly consider the discovery of serial and
parallel episodes.
We now de-ne episodes formally. An episode ff is a triple (V; -; g) where
V is a set of nodes, - is a partial order on V , and mapping
associating each node with an event type. The interpretation of an episode
is that the events in g(V ) have to occur in the order described by -. The
size of ff, denoted jffj, is jV j. Episode ff is parallel if the partial order - is
trivial (i.e., x 6- y for all x; y 2 V such that x 6= y). Episode ff is serial if the
relation - is a total order (i.e., x - y or y - x for all
is injective if the mapping g is an injection, i.e., no event type occurs twice
in the episode.
Example 3 Consider episode Figure 3. The set V contains
two nodes; say x and y. The mapping g labels these nodes with the event
types that are seen in the -gure: An event of type
is supposed to occur before an event of type F , i.e., x precedes y, and we
have x - y. Episode ff is injective, since it does not contain duplicate event
types; in a window where ff occurs there may, however, be multiple events
of types E and F .
We next de-ne when an episode is a subepisode of another; this relation
is used extensively in the algorithms for discovering all frequent episodes. An
there exists an injective mapping
all
ff is a superepisode of fi if and only if fi - ff. We write fi OE ff if fi - ff and
ff 6- fi.
Example 4 From Figure 3 we see that fi - fl since fi is a subgraph of fl.
In terms of the de-nition, there is a mapping f that connects the nodes
labeled A with each other and the nodes labeled B with each other, i.e.,
both nodes of fi have (disjoint) corresponding nodes in fl. Since the nodes in
episode fi are not ordered, the corresponding nodes in fl do not need to be
Consider now what it means that an episode occurs in a sequence. The
nodes of the episode need to have corresponding events in the sequence such
that the event types are the same and the partial order of the episode is
respected. An occurs in an event sequence
if there exists an injective mapping ng from nodes to events,
such that
Example 5 The window (w; 35; 40) of Figure 2 contains events A; B; C;
and E. Episodes fi and fl of Figure 3 occur in the window, but ff does not.
odes, a window width win, a frequency threshold min-fr, and a con-dence
threshold min-conf.
Output: The episode rules that hold in s with respect to win, min-fr, and
min-conf.
1. /* Find frequent episodes (Algorithm 2): */
2. compute F(s; win; min-fr);
3. /* Generate rules: */
4. for all ff 2 F(s; win; min-fr) do
5. for all fi OE ff do
6. if fr(ff)=fr(fi) - min-conf then
7. output the rule fi ! ff and the con-dence fr(ff)=fr(fi);
We de-ne the frequency of an episode as the fraction of windows in
which the episode occurs. That is, given an event sequence s and a window
width win, the frequency of an episode ff in s is
occurs in wgj
Given a frequency threshold min-fr, ff is frequent if fr(ff; s; win) -
min-fr. The task we are interested in is to discover all frequent episodes
from a given class E of episodes. The class could be, e.g., all parallel episodes
or all serial episodes. We denote the collection of frequent episodes with
respect to s, win and min-fr by F(s; win; min-fr).
Once the frequent episodes are known, they can be used to obtain rules
that describe connections between events in the given event sequence. For
example, if we know that the episode fi of Figure 3 occurs in 4.2 % of the
windows and that the superepisode fl occurs in 4.0 % of the windows, we can
estimate that after seeing a window with A and B, there is a chance of about
0.95 that C follows in the same window. Such rules show the connections
between events more clearly than frequent episodes alone. Algorithm 1 shows
how rules and their con-dences can be computed from the frequencies of
episodes, a window width win, and a frequency threshold min-fr.
Output: The collection F(s; win; min-fr) of frequent episodes.
1. compute C 1 := fff
2. l :=
3. while C l 6= ; do
4. /* Database pass (Algorithms 4 and 5): */
5. compute F l := fff 2 C l j fr(ff; s; win) - min-frg;
7. /* Candidate generation (Algorithm 3): */
8. compute C l := fff l and for all fi 2 E such that fi OE ff and
9. l we have fi 2 F jfij
10. for all l do output F l ;
episodes. Note that indentation is used in the algorithms to specify the
extent of loops and conditional statements.
Algorithms
Given all frequent episodes, the rule generation is straightforward. We now
concentrate on the following discovery task: given an event sequence s, a
set E of episodes, a window width win, and a frequency threshold min-fr,
-nd F(s; win; min-fr): We give -rst a speci-cation of the algorithm and
then exact methods for its subtasks. We call these methods collectively the
algorithm.
3.1 Main algorithm
Algorithm 2 computes the collection F(s; win; min-fr) of frequent episodes
from a class E of episodes. The algorithm performs a levelwise (breadth-rst)
search in the episode lattice spanned by the subepisode relation. The search
starts from the most general episodes, i.e., episodes with only one event. On
each level the algorithm -rst computes a collection of candidate episodes,
and then checks their frequencies from the event sequence database. The
crucial point in the candidate generation is given by the following immediate
lemma.
Lemma 6 If an episode ff is frequent in an event sequence s, then all subepis-
odes fi - ff are frequent.
The collection of candidates is speci-ed to consist of episodes such that
all smaller subepisodes are frequent. This criterion safely prunes from consideration
episodes that can not be frequent. More detailed methods for the
candidate generation and database pass phases are given in the following
subsections.
3.2 Generation of candidate episodes
We present now a candidate generation method in detail. The method can
be easily adapted to deal with the classes of parallel episodes, serial episodes,
and injective parallel and serial episodes.
Algorithm 3 computes candidates for parallel episodes. In the algorithm,
an represented as a lexicographically sorted array of
event types. The array is denoted by the name of the episode and the items
in the array are referred to with the square bracket notation. For example,
a parallel episode ff with events of types A; C; C; and F is represented as an
array ff with . Collections of
episodes are also represented as lexicographically sorted arrays, i.e., the ith
episode of a collection F is denoted by F [i].
Since the episodes and episode collections are sorted, all episodes that
share the same -rst event types are consecutive in the episode collection. In
particular, if episodes F l [i] and F l [j] of size l share the -rst l \Gamma 1 events,
then for all k with we have that F l [k] shares also the same
Algorithm 3
Input: A sorted array F l of frequent parallel episodes of size l.
Output: A sorted array of candidate parallel episodes of size l + 1.
1. C l+1 := ;;
2. k := 0;
3. if l = 1 then for h := 1 to jF l j do F l :block-start[h] :=
4. for i := 1 to jF l j do
5. current-block-start
6. for (j :=
7. /* F l [i] and F l [j] have l \Gamma 1 -rst event types in common,
8. build a potential candidate ff as their combination: */
9. for x := 1 to l do ff[x] := F l [i][x];
11. /* Build and test subepisodes fi that do not contain ff[y]: */
12. for y := 1 to l \Gamma 1 do
13. for x := 1 to y \Gamma 1 do fi[x] := ff[x];
14. for x := y to l do fi[x] := ff[x
15. if fi is not in F l then continue with the next j at line 6;
16. /* All subepisodes are in F l , store ff as candidate: */
18. C l+1 [k] := ff;
19. C l+1 :block-start[k] := current-block-start;
events. A maximal sequence of consecutive episodes of size l that share the
-rst events is called a block. Potential candidates can be identi-ed by
creating all combinations of two episodes in the same block. For the eOEcient
identi-cation of blocks, we store in F l :block-start [j] for each episode F l [j]
the i such that F l [i] is the -rst episode in the block.
Algorithm 3 can be easily modi-ed to generate candidate serial episodes.
Now the events in the array representing an episode are in the order imposed
by a total order -. For instance, a serial episode fi with events of types
C; A; F; and C, in that order, is represented as an array fi with
replacing line 6 by
for (j := F l :block-start[i]; F l
Algorithm 3 generates candidates for serial episodes.
There are further options with the algorithm. If the desired episode class
consists of parallel or serial injective episodes, i.e., no episode should contain
any event type more than once, simply insert line
continue with the next j at line 6;
after line 6.
The time complexity of Algorithm 3 is polynomial in the size of the collection
of frequent episodes and it is independent of the length of the event
sequence.
Theorem 1 Algorithm 3 (with any of the above variations) has time complexity
O(l 2 jF l j 2 log jF l j).
Proof The initialization (line j). The outer loop (line
is iterated O(jF l j) times and the inner loop (line times. Within the
loops, a potential candidate (lines 9 and 10) and l \Gamma 1 subcandidates (lines 12
to are built in time O(l importantly, the
subsets need to be searched for in the collection F l (line 15). Since
F l is sorted, each subcandidate can be located with binary search in time
O(l log jF l j). The total time complexity is thus O(jF l j
l log jF l
In practical situations the time complexity is likely to be close to
O(l 2 jF l j log jF l j), since the blocks are typically small.
3.3 Recognizing episodes in sequences
Let us now consider the implementation of the database pass. We give algorithms
which recognize episodes in sequences in an incremental fashion.
For two windows 1), the
sequences w and w 0 of events are similar to each other. We take advantage of
this similarity: after recognizing episodes in w, we make incremental updates
in our data structures to achieve the shift of the window to obtain w 0 .
The algorithms start by considering the empty window just before the
input sequence, and they end after considering the empty window just after
the sequence. This way the incremental methods need no other special actions
at the beginning or end. When computing the frequency of episodes,
only the windows correctly on the input sequence are, of course, considered.
3.3.1 Parallel episodes
Algorithm 4 recognizes candidate parallel episodes in an event sequence. The
main ideas of the algorithm are the following. For each candidate parallel
episode ff we maintain a counter ff:event-count that indicates how many
events of ff are present in the window. When ff:event-count becomes equal
to jffj, indicating that ff is entirely included in the window, we save the
starting time of the window in ff:inwindow . When ff:event-count decreases
again, indicating that ff is no longer entirely in the window, we increase the
-eld ff:freq-count by the number of windows where ff remained entirely in
the window. At the end, ff:freq-count contains the total number of windows
where ff occurs.
To access candidates eOEciently, they are indexed by the number of events
of each type that they contain: all episodes that contain exactly a events of
type A are in the list contains(A,a). When the window is shifted and the
contents of the window change, the episodes that are aoeected are updated.
If, for instance, there is one event of type A in the window and a second
one comes in, all episodes in the list contains(A,2) are updated with the
information that both events of type A they are expecting are now present.
Algorithm 4
Input: A collection C of parallel episodes, an event sequence
a window width win, and a frequency threshold min-fr.
Output: The episodes of C that are frequent in s with respect to win
and min-fr.
1. /* Initialization: */
2. for each ff in C do
3. for each A in ff do
4. A:count := 0;
5. for i := 1 to jffj do contains(A; i) := ;;
6. for each ff in C do
7. for each A in ff do
8. a := number of events of type A in ff;
9.
10. ff.event-count := 0;
11. ff.freq-count := 0;
12. /* Recognition: */
13. for start := T s do
14. /* Bring in new events to the window: */
15. for all events (A; t) in s such that
16. A:count := A:count
17. for each ff 2 contains(A; A:count) do
18. ff:event-count := ff:event-count
19. if ff:event-count = jffj then ff:inwindow := start ;
20. /* Drop out old events from the window: */
21. for all events (A; t) in s such that
22. for each ff 2 contains(A; A:count) do
23. if ff:event-count = jffj then
24. ff:freq-count := ff:freq-count
25. ff:event-count := ff:event-count \Gamma A:count ;
26. A:count := A:count \Gamma
27. /* Output: */
28. for all episodes ff in C do
29. if ff:freq-count=(T
3.3.2 Serial episodes
Serial candidate episodes are recognized in an event sequence by using state
automata that accept the candidate episodes and ignore all other input. The
idea is that there is an automaton for each serial episode ff, and that there
can be several instances of each automaton at the same time, so that the
active states reAEect the (disjoint) pre-xes of ff occurring in the window.
Algorithm 5 implements this idea.
We initialize a new instance of the automaton for a serial episode ff every
time the -rst event of ff comes into the window; the automaton is removed
when the same event leaves the window. When an automaton for ff reaches
its accepting state, indicating that ff is entirely included in the window, and
if there are no other automata for ff in the accepting state already, we save
the starting time of the window in ff:inwindow . When an automaton in the
accepting state is removed, and if there are no other automata for ff in the
accepting state, we increase the -eld ff:freq-count by the number of windows
where ff remained entirely in the window.
It is useless to have multiple automata in the same state, as they would
only make the same transitions and produce the same information. It suOEces
to maintain the one that reached the common state last since it will be
also removed last. There are thus at most jffj automata for an episode ff.
For each automaton we need to know when it should be removed. We can
thus represent all the automata for ff with one array of size jffj: the value
of ff:initialized [i] is the latest initialization time of an automaton that has
reached its ith state. Recall that ff itself is represented by an array containing
its events; this array can be used to label the state transitions.
To access and traverse the automata eOEciently they are organized in the
following way. For each event type A 2 E, the automata that accept A
are linked together to a list waits(A). The list contains entries of the form
(ff; x) meaning that episode ff is waiting for its xth event. When an event
enters the window during a shift, the list waits(A) is traversed. If an
automaton reaches a common state i with another automaton, the earlier
entry ff:initialized [i] is simply overwritten.
The transitions made during one shift of the window are stored in a list
transitions. They are represented in the form (ff; x; t) meaning that episode
Algorithm 5
Input: A collection C of serial episodes, an event sequence
window width win, and a frequency threshold min-fr.
Output: The episodes of C that are frequent in s with respect to win
and min-fr.
1. /* Initialization: */
2. for each ff in C do
3. for i := 1 to jffj do
4. ff:initialized[i] := 0;
5. waits(ff[i]) := ;;
6. for each ff 2 C do
7. waits(ff[1]) := waits(ff[1]) [ f(ff; 1)g;
8. ff.freq-count := 0;
9. for t :=
10. /* Recognition: */
11. for start := T s do
12. /* Bring in new events to the window: */
13. beginsat(start
14. transitions := ;;
15. for all events (A; t) in s such that
16. for all (ff; do
17. if
19. transitions := transitions [ f(ff;
20. else
21. transitions := transitions [ f(ff;
24. ff:initialized
25.
26. for all (ff; j; t) 2 transitions do
27. ff:initialized[j] := t;
28. beginsat(t) := beginsat(t) [ f(ff; j)g;
29.
30. /* Drop out old events from the window: */
31. for all (ff; l) 2 beginsat(start \Gamma 1) do
33. else waits(ff[l
34. ff:initialized[l] := 0;
35. /* Output: */
36. for all episodes ff in C do
37. if ff:freq-count=(T
ff got its xth event, and the latest initialization time of the pre-x of length x
is t. Updates regarding the old states of the automata are done immediately,
but updates for the new states are done only after all transitions have been
identi-ed, in order to not overwrite any useful information. For easy removal
of automata when they go out of the window, the automata initialized at
time t are stored in a list beginsat(t).
3.3.3 Analysis of time complexity
For simplicity, suppose that the class of event types E is -xed, and assume
that exactly one event takes place every time unit. Assume candidate episodes
are all of size l, and let n be the length of the sequence.
Theorem 2 The time complexity of Algorithm 4 is O((n
Proof Initialization takes time O(jCj l 2 ). Consider now the number of the
operations in the innermost loops, i.e., accesses to ff:event-count on lines
and 25. In the recognition phase there are O(n) shifts of the window. In
each shift, one new event comes into the window, and one old event leaves
the window. Thus, for any episode ff, ff:event-count is accessed at most
twice during one shift. The cost of the recognition phase is thus O(n jCj).
In practice the size l of episodes is very small with respect to the size
n of the sequence, and the time required for the initialization can be safely
neglected. For injective episodes we have the following tighter result.
Theorem 3 The time complexity of recognizing injective parallel episodes
in Algorithm 4 (excluding initialization) is O( n
win
Proof Consider win successive shifts of one time unit. During such sequence
of shifts, each of the jCj candidate episodes ff can undergo at most 2l changes:
any event type A can have A:count increased to 1 and decreased to 0 at most
once. This is due to the fact that after an event of type A has come into the
window, A:count - 1 for the next win time units. Reading the input takes
time n.
This time bound should be contrasted with the time usage of a trivial
non-incremental method where the sequence is pre-processed into windows,
and then frequent sets are searched for. The time requirement for recognizing
jCj candidate sets in n windows, plus the time required to read in n windows
of size win, is O(n jCj l larger by a factor of win.
Theorem 4 The time complexity of Algorithm 5 is O(n jCj l):
Proof The initialization takes time O(jCj l +win). In the recognition phase,
again, there are O(n) shifts, and in each shift one event comes into the
window and one event leaves the window. In one shift, the eoeort per an
ff depends on the number of automata accessed; there are a maximum
of l automata for each episode. The worst-case time complexity is thus
(note that win is O(n)).
In the worst case the input sequence consists of events of only one event
type, and the candidate serial episodes consist only of events of that particular
type. Every shift of the window results now in an update in every
automaton. This worst-case complexity is close to the complexity of the
trivial non-incremental method O(n jCj l In practical situations,
however, the time requirement is considerably smaller, and we approach the
savings obtained in the case of injective parallel episodes.
Theorem 5 The time complexity of recognizing injective serial episodes in
Algorithm 5 (excluding initialization) is O(n jCj):
Proof Each of the O(n) shifts can now aoeect at most two automata for
each episode: when an event comes into the window there can be a state
A
A

Figure

4: Recursive composition of a complex episode.
transition in at most one automaton, and at most one automaton can be
removed because the initializing event goes out of the window.
3.4 General partial orders
So far we have only discussed serial and parallel episodes. We next discuss
brieAEy the use of other partial orders in episodes. The recognition of an
arbitrary episode can be reduced to the recognition of a hierarchical combination
of serial and parallel episodes. For example, episode fl in Figure 4
is a serial combination of two episodes: a parallel episode ffi 0 consisting of
A and B, and an episode ffi 00 consisting of C alone. The occurrence of an
episode in a window can be tested using such hierarchical structure: to see
whether episode fl occurs in a window one checks (using a method for serial
whether the subepisodes ffi 0 and ffi 00 occur in this order; to check the
occurrence of ffi 0 one uses a method for parallel episodes to verify whether A
and B occur.
There are, however, some complications one has to take into account.
First, it is sometimes necessary to duplicate an event node to obtain a decomposition
to serial and parallel episodes. Duplication works easily with
injective episodes, but non-injective episodes need more complex methods.
Another important aspect is that composite events have a duration, unlike
the elementary events in E.
A practical alternative is to handle all episodes basically like parallel
episodes, and to check the correct partial ordering only when all events are
in the window. Parallel episodes can be located eOEciently; after they have
been found, checking the correct partial ordering is relatively fast.
4 An alternative occurrence

4.1 Outline of the approach
In this section we describe an alternative approach to the discovery of epis-
odes. Instead of looking at the windows and only considering whether an
occurs in a window or not, we now look at the exact occurrences of
episodes and the relationships between those occurrences. One of the advantages
of this new approach is that focusing on the occurrences of episodes
allows us to more easily -nd rules with two window widths, one for the left-hand
side and one for the whole rule, such as iif A and B occur within 15
seconds, then C follows within
The approach is based on minimal occurrences of episodes. Besides the
new rule formulation, the use of minimal occurrences gives raise to the following
new method, called Minepi, for the recognition of episodes in the input
sequence. For each frequent episode we store information about the locations
of its minimal occurrences. In the recognition phase we can then compute
the locations of minimal occurrences of a candidate episode ff as a temporal
join of the minimal occurrences of two subepisodes of ff. In addition to being
simple and eOEcient, this formulation has the advantage that the con-dences
and frequencies of rules with a large number of dioeerent window widths can
be obtained quickly, i.e., there is no need to rerun the analysis if one only
wants to modify the window widths. In the case of complicated episodes,
the time needed for recognizing the occurrence of an episode can be signi-c-
ant; the use of stored minimal occurrences of episodes eliminates unnecessary
repetition of the recognition eoeort.
We identify minimal occurrences with their time intervals in the following
way. Given an episode ff and an event sequence s, we say that the interval
occurrence of ff in s, if (1) ff occurs in the window
e ) on s, and if (2) ff does not occur in any proper subwindow on
i.e., not in any window w
e ) on s such that t s - t 0
s
e
width(w). The set of (intervals of) minimal occurrences of an
episode ff in a given event sequence is denoted by mo(ff):
occurrence of ffg:
Example 7 Consider the event sequence s in Figure 2 and the episodes in

Figure

3. The parallel episode fi consisting of event types A and B has
four minimal occurrences in s:
The partially ordered episode fl has the following three minimal occurrences:
An episode rule is an expression fi [win 1 are
episodes such that fi - ff, and win 1 and win 2 are integers. The informal
interpretation of the rule is that if episode fi has a minimal occurrence at
interval occurs at interval [t s
for some t 0
e
such that t 0
e
. Formally this can be expressed in the
following way. Given win 1 and fi, denote mo win 1
and an interval [u s ; u e ), de-ne occ(ff; [u s ; u e
true if and only if there exists a minimal occurrence [u 0
s
and
e
- u e . The con-dence of an episode rule fi [win 1
is now
Example 8 Continuing the previous example, we have, e.g., the following
rules and con-dences. For the rule fi [3] ) fl [4] we have
in the denominator and jf[35; 38)gj in the nu-
merator, so the con-dence is 1=3. For the rule fi [3] ) fl [5] the con-dence
is 1.
Note that since fi is a subepisode of ff, the rule right-hand side ff contains
information about the relative location of each event in it, so the inewj events
in the rule right-hand side can actually be required to be positioned, e.g.,
between events in the left-hand side. There is also a number of possible
de-nitions for the temporal relationship between the intervals. For instance,
rules that point backwards in time can be de-ned in a similar way. For
brevity, we only consider this one case.
We de-ned the frequency of an episode as the fraction of windows that
contain the episode. While frequency has a nice interpretation as the probability
that a randomly chosen window contains the episode, the concept is
not very useful with minimal occurrences: (1) there is no -xed window size,
and (2) a window may contain several minimal occurrences of an episode.
Instead of frequency, we use the concept of support, the number of minimal
occurrences of an episode: the support of an episode ff in a given event sequence
s is jmo(ff)j. Similarily to the a frequency threshold, we now use a
threshold for the support: given a support threshold min-sup, an episode ff
is frequent if jmo(ff)j - min-sup.
The current episode rule discovery task can be stated as follows. Given
an event sequence s, a class E of episodes, and a set W of time bounds, -nd
all frequent episode rules of the form fi [win 1
4.2 Finding minimal occurrences of episodes
In this section we describe informally the collection Minepi of algorithms
that locate the minimal occurrences of frequent serial and parallel episodes.
Let us start with some observations about the basic properties of episodes.
Lemma 6 still holds: the subepisodes of a frequent episode are frequent. Thus
we can use the main algorithm (Algorithm 2) and the candidate generation
(Algorithm We have the following results about the
minimal occurrences of an episode also containing minimal occurrences of its
subepisodes.
Lemma 9 Assume ff is an episode and fi - ff is its subepisode. If
mo(ff), then fi occurs in [t s ; t e ) and hence there is an interval [u s ;
such that t s -
ff be a serial episode of size k, and let [t
there are subepisodes ff 1 and ff 2 of ff of size
for some t 1
Lemma 11 Let ff be a parallel episode of size k, and let [t
Then there are subepisodes ff 1 and ff 2 of ff of size
e
s
and t
e
g.
The minimal occurrences of a candidate episode ff are located in the
following way. In the -rst iteration of the main algorithm, mo(ff) is computed
from the input sequence for all episodes ff of size 1. In the rest of the
iterations, the minimal occurrences of a candidate ff are located by -rst
selecting two suitable subepisodes ff 1 and ff 2 of ff, and then computing a
temporal join between the minimal occurrences of ff 1 and ff 2 , in the spirit of
To be more speci-c, for serial episodes the two subepisodes are selected
so that ff 1 contains all events except the last one and ff 2 in turn contains all
except the -rst one. The minimal occurrences of ff are then found with the
following speci-cation:
such that t s ! u
For parallel episodes, the subepisodes ff 1 and ff 2 contain all events except
one; the omitted events must be dioeerent. See Lemma 11 for the idea of how
to compute the minimal occurrences of ff.
The minimal occurrences of a candidate episode ff can be found in a linear
pass over the minimal occurrences of the selected subepisodes ff 1 and ff 2 . The
time required for one candidate is thus O(jmo(ff
which is O(n), where n is the length of the event sequence. To optimize
the running time, ff 1 and ff 2 can be selected so that jmo(ff 1 )j
minimized.
The space requirement of the algorithm can be expressed as
jmo(ff)j, assuming the minimal occurrences of all frequent episodes
are stored, or alternatively as
jmo(ff)j), if only the current
and next levels of minimal occurrences are stored. The size of P
is bounded by n, the number of events in the input sequence, as each event
in the sequence is a minimal occurrence of an episode of size 1. In the second
iteration, an event in the input sequence can start at most jF 1 j minimal occurrences
of episodes of size 2. The space complexity of the second iteration
is thus O(jF 1 jn).
While minimal occurrences of episodes can be located quite eOEciently,
the size of the data structures can be even larger than the original database,
especially in the -rst couple of iterations. A practical solution is to use in the
beginning other pattern matching methods, e.g., similar to the ones given for
in Section 3, to locate the minimal occurrences.
Finally, note that Minepi can be used to solve the task of Winepi.
Namely, a window contains an occurrence of an episode exactly when it
contains a minimal occurrence. The frequency of an episode ff can thus be
computed from mo(ff).
4.3 Finding con-dences of rules
We now show how the information about minimal occurrences of frequent
episodes can be used to obtain con-dences for various types of episode rules
without looking at the data again.
Recall that we de-ned an episode rule as an expression fi [win 1
ff [win 2 ]; where fi and ff are episodes such that fi - ff, and win 1 and win 2 are
integers. To -nd such rules, -rst note that for the rule to be frequent, the
episode ff has to be frequent. So rules of the above form can be enumerated
by looking at all frequent episodes ff, and then looking at all subepisodes fi
of ff. The evaluation of the con-dence of the rule fi [win 1
be done in one pass through the structures mo(fi) and mo(ff), as follows.
For each locate the minimal occurrence
of ff such that t s - u s and [u s ; u e ) is the -rst interval in mo(ff) with
this property. Then check whether u
The time complexity of the con-dence computation for a given episode
and given time bounds win 1 and win 2 is O(jmo(fi)j jmo(ff)j). The con-
-dences for all win in the set W of time bounds can be found, using
a table of size jWj 2 , in time O(jmo(fi)j For reasons of
brevity we omit the details.
The set W of time bounds can be used to restrict the initial search of minimal
occurrences of episodes. Given W, denote the maximum time bound by
In episode rules, only occurrences of at most win
units can be used; longer episode occurrences can thus be ignored already in
the search of frequent episodes. We consider the support, too, to be computed
with respect to a given win max .
5 Experiments
We have run a series of experiments using Winepi and Minepi. The general
performance of the methods, the eoeect of the various parameters, and the
scalability of the methods are considered in this section. Consideration is
also given to the applicability of the methods to various types of data sets.
The experiments have been run on a PC with 166 MHz Pentium processor
and main memory, under the Linux operating system. The sequences
resided in a AEat text -le.
5.1 Performance overview
For an experimental overview we discovered episodes and rules in a telecommunication
network fault management database. The database is a sequence
of 73679 alarms covering a time period of 7 weeks. There are 287 dioeerent
types of alarms with very diverse frequencies and distributions. On the average
there is an alarm every minute. However, the alarms tend to occur in
bursts: in the extreme cases there are over 40 alarms in one second.
We start by looking at the performance of the Winepi method described
in Section 3. There are several performance characteristics that can be used
to evaluate the method. The time required by the method and the number
of episodes and rules found by the method, with respect to the frequency
threshold or the window width, are possible performance measures. We
present results for the two opposite extreme cases of the complexity: serial
episodes and injective parallel episodes.

Tables

-nding frequent episodes
in the alarm database with various frequency thresholds. The number
of frequent episodes decreases rapidly as the frequency threshold increases.
With a given frequency threshold, the numbers of serial and injective parallel
episodes may be fairly similar, e.g., a frequency threshold of 0.002 results in
Frequency Candidates Frequent Iterations Total
threshold Episodes time

Table

1: Performance characteristics for serial episodes with
database, window width
Frequency Candidates Frequent Iterations Total
threshold Episodes time

Table

2: Performance characteristics for injective parallel episodes with
serial episodes or 93 parallel episodes. The actual episodes are, however,
very dioeerent, as can be seen from the number of iterations: recall that each
iteration l produces episodes of size l. For the frequency threshold of 0.002,
the longest frequent serial episode consists of 43 events (all candidates of the
last iteration were infrequent), while the longest frequent injective parallel
episodes have 3 events. The number of iterations equals the number of candidate
generation phases. The number of database passes equals the number
of iterations, or is smaller by one when there were no candidates in the last
iteration.
Episodes
Window width

Figure

5: Number of frequent serial (solid line) and injective parallel (dotted
line) episodes as a function of the window width; Winepi, alarm database,
frequency threshold 0:002.
The eoeect of the window width on the number of frequent episodes is
represented in Figure 5. For each window width, there are considerably fewer
frequent injective parallel episodes than frequent serial episodes. With the
alarm data, the increase in the number of episodes is fairly even throughout
the window widths that we considered. However, we will later show that this
may depend heavily on the type of data we are using.

Figure

6 represents the number of serial and injective parallel episodes
found by the method, and Figure 7 the total processing time required, as
the frequency threshold increases. Both curves decrease steeply with the
increasing frequency threshold. The time requirement is much smaller for
parallel episodes than for serial episodes with the same threshold. There
are two reasons for this. The parallel episodes are considerably shorter (see

Tables

1 and 2) and hence, fewer database passes are needed. The complexity
of recognizing injective parallel episodes is also smaller.
Episodes
Frequency threshold

Figure

Number of frequent serial (solid line) and injective parallel (dotted
line) episodes as a function of the frequency threshold with
database, window width
Time
Frequency threshold

Figure

7: Processing time for serial (solid line) and injective parallel (dot-
ted line) episodes as a function of the frequency threshold; Winepi, alarm
database, window width
5.2 Quality of candidate generation
We now take a closer look at the candidates considered and frequent episodes
found during the iterations of the procedure. As an example, let us look at
what happens during the -rst iterations. Statistics of the -rst ten iterations
Episode Episodes Candidates Frequent Match
size episodes

Table

3: Number of candidate and frequent serial episodes during the -rst
ten iteration phases with Winepi; alarm database, frequency threshold 0:001,
window width
of a run with a frequency threshold of 0.001 and a window width of 60 s is
shown in Table 3.
The three -rst iterations dominate the behavior of the method. During
these phases, the number of candidates is large, and only a small fraction
(less than 20 per cent) of the candidates turns out to be frequent. After the
third phase the candidate generation is eOEcient, few of the candidates are
found infrequent, and although the total number of iteration phases is 45,
the last 35 iterations involve only 1-3 candidates each. Thus we could safely
combine several of the later iteration steps, to reduce the number of database
passes.
If we take a closer look at the frequent episodes, we observe that all
frequent episodes longer than 7 events consist of repeating occurrences of
two very frequent alarms. Each of these two alarms occurs in the database
more than 12000 times (16 per cent of the events each).
Support Candidates Frequent Iterations Total
threshold Episodes time
50 12732 2735 83 28
500 813 138
1000 589 92 48 14
2000 405 64

Table

4: Performance characteristics for serial episodes with Minepi; alarm
database, maximum time bound 60 s.
Support Candidates Frequent Iterations Total
threshold Episodes time
100 4376 1755 71 20
500 633 138
1000 480 89 48 12
2000 378 66

Table

5: Performance characteristics for parallel episodes with Minepi; alarm
database, maximum time bound 60 s.
5.3 Comparison of algorithms Winepi and Minepi

Tables

4 and 5 represent performance statistics for -nding frequent episodes
with Minepi, the method using minimal occurences. Compared to the corresponding
-gures for Winepi in Tables 1 and 2, we observe the same general
tendency for a rapidly decreasing number of candidates and episodes, as the
support threshold increases.
The episodes found by Winepi and Minepi are not necessarily the same.
If we compare the cases in Tables 1 and 4 with approximately the same
number of frequent episodes, e.g., 151 serial episodes for Winepi and 138 for
Time
Support threshold

Figure

8: Processing time for serial (solid line) and injective parallel (dotted
line) episodes with Minepi; alarm database, maximum time bound 60 s.
Minepi, we notice that they do not correspond to the same episodes. The
sizes of the longest freuquent episodes are somewhat dioeerent (43 for the
original, 48 for the minimal occurrence method). The frequency threshold
corresponds, at the minimum, to about 150 instances of the
episode, while the support threshold used for Minepi is 500. The dioeerence
between the methods is very clear for small episodes. Consider an episode ff
consisting of just one event A. Winepi considers a single event A to occur in
windows of width 60 s, while Minepi sees only one minimal occurrence.
On the other hand, two successive events of type A result in ff occuring in
61 windows, but the number of minimal occurrences is doubled from 1 to 2.

Figure

8 shows the time requirement for -nding frequent episodes with
Minepi. The processing time for Minepi reaches a plateau when the size of
the maximal episodes no longer changes (in this case, at support threshold
500). The behavior is similar for serial and parallel episodes. The time
requirements of Minepi should not be directly compared to Winepi: the
episodes discovered are dioeerent, and our implementation of Minepi works
entirely in the main memory. With very large databases this might not be
Varying support threshold,
four time bounds
Support Distinct Rule gen.
threshold rules time
50 50470 149
1000 1221 15
2000 1082 14
4000 1005 14
Varying number of time bounds,
support threshold 1000
Number of All Rule gen.
time bounds rules time

Table

Number of rules and rule generation time with Minepi; alarm data-
base, serial episodes, support threshold 1000, maximum time bound 60 s,
con-dence threshold 0.
possible during the -rst iterations; either the minimal occurrences need to
be stored on the disk, or other methods (e.g., variants of Algorithms 4 and
must be used.
5.4 Rules
The methods can easily produce very large amounts of rules. Recall that rules
are constructed by considering all frequent episodes ff as the right-hand side
and all subepisodes fi - ff as the left-hand side of the rule. Additionally,
considers variations of these rules with all the time bounds in the
given set W.

Table

6 represents results with serial episodes. The initial episode generation
with Minepi took around 14 s, and the total number of frequent episodes
was 92. The table shows the number of rules obtained by Minepi with con-
-dence threshold 0 and with maximum time bound 60 s. On the left, with
a varying support threshold, rules that dioeer only in their time bounds are
excluded from the -gures; the rule generation time is, however, obtained by
generating rules with four dioeerent time bounds.
Rules
Confindence threshold

Figure

9: Total number of distinct rules found by Minepi with various con-
-dence thresholds; alarm database, maximum time bound 60 s, support
threshold 100.
The minimal occurrence method is particularly useful, if we are interested
in -nding rules with several dioeerent time bounds. The right side of Table 6
represents performance results with a varying number of time bounds. The
time requirement increases slowly as more time bounds are used, and the
time increases slowlier than the number of rules.
The amount of almost 80000 rules, obtained with may
seem unnecessarily large and unjusti-ed. Remember, however, that there are
only 1221 distinct rules. The rest of the rules present dioeerent combinations
of time bounds, in this case down to the granularity of one second. For
the cost of 43 s we thus obtain very -ne-grained rules from our frequent
episodes. Dioeerent criteria can then be used to select the most interesting
rules from these. Figure 9 represents the eoeect of the con-dence threshold to
the number of distinct rules found by Minepi. Although the initial number of
rules may be quite large, it decreases fairly rapidly if we require a reasonable
con-dence.
Data set Events Event Supp. Max Conf. Freq. Rules
name types thr. time b. thr. epis.
alarms 73679 287 100
protein

Table

7: Characteristic parameter values for each of the data sets and the
number of episodes and rules found by Minepi.
5.5 Results with dioeerent data sets
In addition to the experiments on the alarm database, we have run Minepi
on a variety of dioeerent data collections to get a better view of the usefulness
of the method. The data collections that were used, some typical parameter
values for them, and some results are presented in Table 7.
The WWW data is part of the WWW server log from the Department of
Computer Science at the University of Helsinki. The log contains requests
to WWW pages at the department's server; such requests can be made by
WWW browsers at any host in the Internet. We consider the WWW page
fetched as the event type. The number of events in our data set is 116308,
covering three weeks in February and March, 1996. In total, 7634 dioeerent
pages are referred to. Requests for images have been excluded from consideration

Suitable support thresholds vary a lot, depending on the number of events
and the distribution of event types. A suitable maximum time bound for the
device generated alarm data is one minute, while the slower pace of a human
user requires using a larger time bound (two minutes or more) for the WWW
log. By using a relatively small time bound we reduce the probability of
unrelated requests contributing to the support. A low con-dence threshold
for the WWW log is justi-ed since we are interested in all fairly usual patterns
of usage, not only in the dominating ones. In the WWW server log we found,
e.g., long often used paths of pages from the home page of the department
to the pages of individual courses. Such behavior suggests that rather than
using a bookmark directly to the home page of a course, many users quickly
navigate there from the departmental home page.
The two text data collections are modi-cations of the same English text.
Each word is considered an event, and the words are indexed consecutively
to give a itimej for each event. The end of each sentence causes a gap
in the indexing scheme, to correspond to a longer distance between words
in dioeerent sentences. We used text from GNU man pages (the gnu awk
manual). The size of the original text (text1) is 5417 words, and the size of
the condensed text -le (text2), where noninformative words such as articles,
prepositions, and conjunctions, have been stripped ooe, is 2871 words. The
number of dioeerent words in the original and the condensed text is 1102,
resp. 905.
For text analysis, there is no point in using large time bounds, since it
is unlikely that there is any connection between words that are not fairly
close to each other. This can be clearly seen in Figure 10 which represents
the number of episodes found on various window widths using Winepi. This
-gure reveals behavior that is distinctively dioeerent from the corresponding

Figure

5 for the alarm database. We observe that for the text data, the
window widths from 24 to 50 produce practically the same amount of serial
episodes. The number of episodes will only increase with considerably larger
window widths. For this data, the interesting frequent episodes are smaller
than 24, while the episodes found with much larger window widths are noise.
The same phenomenon can be observed for parallel episodes.
Only few rules can be found in text using a simple analysis like this.
The strongest rules in the original text involve either the word igawkj, or
Episodes
Window width

Figure

10: Number of serial (solid line) and injective parallel (dotted line)
episodes as a function of the window width; Winepi, compressed text data
(text2), frequency threshold 0:02.
common phrases such as
the, value [2] ) of [3] (con-dence 0.90)
meaning that in 90 % of the cases where the words ithe valuej are consec-
utive, they are immediately followed by the preposition iofj. These rules
were not found in the condensed text since all prepositions and articles have
been stripped ooe. The few rules in the condensed text contain multiple occurrences
of the word igawkj, or combinations of words occurring in the
header of each man page, such as ifree softwarej.
We performed scale-up tests with 5, 10, and 20 fold multiples of the
compressed text -le, i.e., sequences of approximately 2900 to 58000 events.
The results in Figure 11 show that the time requirement is roughly linear
with respect to the length of the input sequence, as could be expected.
Finally, we experimented with protein sequences. We used data in the
database [1] of the ExPASy WWW molecular biology server of the
Geneva University Hospital and the University of Geneva [11]. PROSITE
contains biologically signi-cant DNA and protein patterns that help to
Time
Relative size of database
r
r
r
r

Figure

11: Scale-up results for serial (solid line) and injective parallel (dotted
line) episodes with Minepi; compressed text data, maximum time bound 60,
threshold 10 for the smallest -le (n-fold for the larger -les).
identify to which family of protein (if any) a new sequence belongs. The
purpose of our experiment is to evaluate our algorithm against an external
data collection and patterns that are known to exist, not to -nd patterns
previously unknown to the biologists. We selected as our target a family of
7 sequences (iDNA mismatch repair proteins 1j, PROSITE entry PS00058).
The sequences in the family are known to contain the string GFRGEAL of seven
consequtive symbols. We transformed the data in a manner similar to the
English text: symbols are indexed consecutively, and between the protein
sequences we place a gap. The total length of this data set is 4941 events,
with an alphabet of 22 event types. The method could be easily modi-ed to
take several separage sequences as input, and to compute the support of an
ff, e.g., as the number of input sequences that contain a (minimal)
occurrence of ff of length at most the maximum time bound.
The parameter values for the protein database are chosen on purpose to
reveal the pattern that is known to be present in the database. The window
width was selected to be 10, i.e., slightly larger than the length of the pattern
that we were looking for, and the support threshold was set to 7, for the
seven individual sequences in the original data. With this data, we are only
interested in the longest episodes (of length 7 or longer). Of the more than
20000 episodes found, 17 episodes are of length 7 or 8. As expected, these
contain the sequence GFRGEAL that was known to be in the database. The
longer episodes are variants of this pattern with an eighth symbol fairly near,
but not necessarily immediately subsequent to the pattern (e.g., GFRGEAL*S).
These types of patterns belong to the pattern class used in PROSITE but, to
our suprise, these longer patterns are not reported in the PROSITE database.
6 Extensions and related work
The task of discovering frequent parallel episodes can be stated as a task
of discovering all frequent sets, a central phase of discovering assocation
rules [2], the rule generation methods are also basically the same for association
rules and Winepi. The levelwise main algorithm has also been used
successfully in the search of frequent sets [3].
Technical problems related to the recognition of episodes have been researched
in several -elds. Taking advantage of the slowly changing contents
of the group of recent events has been studied, e.g., in arti-cial intelligence,
where a similar problem in spirit is the many pattern/many object pattern
match problem in production system interpreters [9]. Also, comparable
strategies using a sliding window have been used, e.g., to study the locality
of reference in virtual memory [7]. Our setting dioeers from these in that
our window is a queue with the special property that we know in advance
when an event will leave the window; this knowledge is used by Winepi in
the recognition of serial episodes. In Minepi, we take advantage of the fact
that we know where subepisodes of candidates have occurred.
The recent work on sequence data in databases (see [21]) provides interesting
openings towards the use of database techniques in the processing of
queries on sequences. A problem similar to the computation of frequencies
occurs also in the area of active databases. There triggers can be speci-ed
as composite events, somewhat similar to episodes. In [10] it is shown how
-nite automata can be constructed from composite events to recognize when
a trigger should be -red. This method is not practical for episodes since the
deterministic automata could be very large.
The methods for matching sets of episodes against a sequence have some
similarities to the algorithms used in string matching (e.g., [12]). In par-
ticular, recognizing serial episodes in a sequence can be seen as locating all
occurrences of subsequences, or matches of patterns with variable length
don't care symbols, where the length of the occurrences is limited by the
window width. Learning from a set of sequences has received considerable
interest in the -eld of bioinformatics, where an interesting problem is the
discovery of patterns common to a set of related protein or amino acid se-
quences. The classes of patterns dioeer from ours; they can be, e.g., substrings
with -xed length don't care symbols [15]. Closer to our patterns are those
considered in [24]. The described algorithm -nds patterns that are similar
to serial episodes; however, the patterns have a given minimum length, and
the occurrences can be within a given edit distance. Recent results on the
pattern matching aspects of recognizing episodes can be found in [6].
The work most closely related to ours is perhaps [4]. There multiple
sequences are searched for patterns that are similar to the serial episodes
with some extra restrictions and an event taxonomy. Our methods can be
extended with a taxonomy by a direct application of the similar extensions to
association rules [13, 14, 22]. Also, our methods can be applied on analyzing
several sequencies; there is actually a variety of choices for the de-nition of
frequency of an episode in a set of sequencies. More recently, the pattern
class of [4] has been extended with windowing, some extra time constraints,
and an event taxonomy [23]. - For a survey on patterns in sequential data,
see [17].
In stochastics, event sequence data is often called a marked point process
[16]. It should be noted that traditional methods for analyzing marked
point processes are ill suited for the cases where the number of event types
is large. However, there exists an interesting combination of techniques: frequent
episodes are discovered -rst, and then the phenomena they describe
are analyzed in more detail with methods for marked point processes.
There are also some interesting similarities between the discovery of frequent
episodes and the work done on inductive logic programming (see,
e.g., [20]); a noticeable dioeerence is caused by the sequentiality of the underlying
data model, and the emphasis on time-limited occurrences. Similarly,
the problem of looking for one occurrence of an episode can be viewed as a
constraint satisfaction problem.
The class of patterns discovered can be easily modi-ed in several direc-
tions. Dioeerent windowing strategies could be used, e.g., considering only
windows starting every win 0 time units for some win 0 , or windows starting
from every event. Other types of patterns could also be searched for, e.g.,
substrings with -xed length don't care symbols; searching for episodes in
several sequences is no problem. A more general framework for episode discovery
has been presented in [18]. There episodes are de-ned as combinations
of events satisfying certain user speci-ed unary of binary conditions.
Conclusions
We presented a framework for discovering frequent episodes in sequential
data. The framework consists of de-ning episodes as partially ordered sets
of events, and looking at windows on the sequence. We described an al-
gorithm, Winepi, for -nding all episodes from a given class of episodes that
are frequent enough. The algorithm was based on the discovery of episodes
by only considering an episode when all its subepisodes are frequent, and
on incremental checking of whether an episode occurs in a window. The
implementation shows that the method is eOEcient. We have applied the
method in the analysis of the alarm AEow from telecommunication networks,
and discovered episodes have been embedded in alarm handling software.
We also presented an alternative approach, Minepi, to the discovery of
frequent episodes, based on minimal occurrences of episodes. This approach
supplies more power for representing connections between events, as it produces
rules with two time bounds.
Both rule formalisms have their advantages. While the rules of Minepi
are often more informative, the frequencies and con-dences of the rules of
have nice interpretations as probabilities concerning randomly chosen
windows. For a large part the algorithms are similar, there are signi-cant
dioeerences only in the computation of the frequency or support. Roughly,
a general tendency in the performance is that Winepi can be more eOEcient
in the -rst phases of the discovery, mostly due to smaller space requirement.
In the later iterations, Minepi is likely to outperform Winepi clearly. The
methods can be modi-ed for cross-use, i.e., Winepi for -nding minimal occurrences
and Minepi for counting windows, and for some large problems -
whether the rule type of Winepi or Minepi - a mixture of the two methods
could give better performance than either alone.
Interesting extensions to the work presented here are facilities for rule
querying and compilation, i.e., methods by which the user could specify the
class in high-level language and the de-nition would automatically
be compiled into a specialization of the algorithm that would take advantage
of the restrictions on the episode class. Other open problems include the
combination of episode techniques with marked point processes and intensity
models.



--R


Mining association rules between sets of items in large databases.
Fast discovery of association rules.
Mining sequential patterns.
Testing complex temporal relationships involving multiple granularities and its application to data mining.

The working set model of program behavior.
Situation recognition: Representation and algorithms.
A fast algorithm for the many pattern/many object pattern match problem.
Composite event speci-ca- tion in active databases
Geneva University Hospital and University of Geneva
Simple and eOEcient string matching with k mismatches.
Discovery of multiple-level association rules from large databases
A perspective on databases and data mining.
Finding AEexible patterns in unaligned protein sequences.
The Statistical Analysis of Failure Time Data.
Identifying and using patterns in sequential data.
Discovering generalized episodes using minimal occurrences.
An algebraic formulation of temporal knowledge for reasoning about recurring events.
Inductive Logic Programming.

Mining generalized association rules.
Mining sequential patterns: Generalizations and performance improvements.
Combinatorial pattern discovery for scienti-c data: Some preliminary results
--TR

--CTR
Srivatsan Laxman , P. S. Sastry , K. P. Unnikrishnan, Discovering Frequent Episodes and Learning Hidden Markov Models: A Formal Connection, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1505-1517, November 2005
Jia-Wei Han , Jian Pei , Xi-Feng Yan, From sequential pattern mining to structured pattern mining: a pattern-growth approach, Journal of Computer Science and Technology, v.19 n.3, p.257-279, May 2004
Sandra de Amo , Daniel A. Furtado, First-order temporal pattern mining with regular expression constraints, Data & Knowledge Engineering, v.62 n.3, p.401-420, September, 2007
Tomoyuki Morita , Yasushi Hirano , Yasuyuki Sumi , Shoji Kajita , Kenji Mase, A pattern mining method for interpretation of interaction, Proceedings of the 7th international conference on Multimodal interfaces, October 04-06, 2005, Torento, Italy
S. Parthasarathy , M. J. Zaki , M. Ogihara , S. Dwarkadas, Incremental and interactive sequence mining, Proceedings of the eighth international conference on Information and knowledge management, p.251-258, November 02-06, 1999, Kansas City, Missouri, United States
Jian Pei , Jiawei Han , Wei Wang, Mining sequential patterns with constraints in large databases, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Jiawei Han , Jian Pei , Behzad Mortazavi-Asl , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, FreeSpan: frequent pattern-projected sequential pattern mining, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.355-359, August 20-23, 2000, Boston, Massachusetts, United States
Mohammed J. Zaki, Sequence mining in categorical domains: incorporating constraints, Proceedings of the ninth international conference on Information and knowledge management, p.422-429, November 06-11, 2000, McLean, Virginia, United States
Ann Devitt , Joseph Duffin , Robert Moloney, Topographical proximity for mining network alarm data, Proceeding of the 2005 ACM SIGCOMM workshop on Mining network data, August 26-26, 2005, Philadelphia, Pennsylvania, USA
Liping Ji , Kian-Lee Tan , Anthony K. H. Tung, Mining frequent closed cubes in 3D datasets, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Zdenk Tronek, Episode directed acyclic subsequence graph, Nordic Journal of Computing, v.11 n.1, p.35-40, Spring 2004
Roy Villafane , Kien A. Hua , Duc Tran , Basab Maulik, Knowledge Discovery from Series of Interval Events, Journal of Intelligent Information Systems, v.15 n.1, p.71-89, JulyAug. 2000
Katharina Morik, Applications of knowledge discovery, Proceedings of the 18th international conference on Innovations in Applied Artificial Intelligence, p.1-5, June 22-24, 2005, Bari, Italy
Ming-Yen Lin , Suh-Yin Lee, Interactive sequence discovery by incremental mining, Information SciencesInformatics and Computer Science: An International Journal, v.165 n.3-4, p.187-205, 19 October 2004
Kenji Yamanishi , Yuko Maruyama, Dynamic syslog mining for network failure monitoring, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Heikki Mannila , Christopher Meek, Global partial orders from sequential data, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.161-168, August 20-23, 2000, Boston, Massachusetts, United States
Ming-Yen Lin , Suh-Yin Lee, Efficient mining of sequential patterns with time constraints by delimited pattern growth, Knowledge and Information Systems, v.7 n.4, p.499-514, May 2005
Anthony K.H. Tung , Hongjun Lu , Jiawei Han , Ling Feng, Breaking the barrier of transactions: mining inter-transaction association rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.297-301, August 15-18, 1999, San Diego, California, United States
Helen Pinto , Jiawei Han , Jian Pei , Ke Wang , Qiming Chen , Umeshwar Dayal, Multi-dimensional sequential pattern mining, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
Minghua Zhang , Ben Kao , David W. Cheung , Kevin Y. Yip, Mining periodic patterns with gap requirement from sequences, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
Ke Wang , Yabo Xu , Jeffrey Xu Yu, Scalable sequential pattern mining for biological sequences, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
Robert Gwadera , Mikhail J. Atallah , Wojciech Szpankowski, Reliable detection of episodes in event sequences, Knowledge and Information Systems, v.7 n.4, p.415-437, May 2005
Alberto Apostolico , Mikhail J. Atallah, Compact recognizers of episode sequences, Information and Computation, v.174 n.2, p.180-192, May 1 2002
Gong Chen , Xindong Wu , Xingquan Zhu, Mining sequential patterns across time sequences, New Generation Computing, v.26 n.1, p.75-96, January 2008
Foto Afrati , Aristides Gionis , Heikki Mannila, Approximating a collection of frequent sets, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
Kuo-Yu Huang , Chia-Hui Chang, SMCA: A General Model for Mining Asynchronous Periodic Patterns in Temporal Databases, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.774-785, June 2005
Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Using association rules for fraud detection in web advertising networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Mohammad El-Ramly , Eleni Stroulia , Paul Sorenson, Recovering software requirements from system-user interaction traces, Proceedings of the 14th international conference on Software engineering and knowledge engineering, July 15-19, 2002, Ischia, Italy
Jian Pei , Jiawei Han , Wei Wang, Constraint-based sequential pattern mining: the pattern-growth methods, Journal of Intelligent Information Systems, v.28 n.2, p.133-160, April     2007
Chang-Shing Lee , Yuan-Fang Kao , Yau-Hwang Kuo , Mei-Hui Wang, Automated ontology construction for unstructured text documents, Data & Knowledge Engineering, v.60 n.3, p.547-566, March, 2007
R. B. V. Subramanyam , A. Goswami, A fuzzy data mining algorithm for incremental mining of quantitative sequential patterns, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.13 n.6, p.633-652, December 2005
Wei Wang , Jiong Yang , Philip S. Yu, Mining patterns in long sequential data with noise, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.28-33, Dec. 2000
Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Jianyong Wang , Helen Pinto , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach, IEEE Transactions on Knowledge and Data Engineering, v.16 n.11, p.1424-1440, November 2004
Andrzej Skowron , Piotr Synak, Reasoning in information maps, Fundamenta Informaticae, v.59 n.2-3, p.241-259, February 2004
Gregory Buehrer , Srinivasan Parthasarathy , Amol Ghoting, Out-of-core frequent pattern mining on a commodity PC, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
Hewijin Christine Jiau , Yi-Jen Su , Yeou-Min Lin , Shang-Rong Tsai, MPM: a hierarchical clustering algorithm using matrix partitioning method for non-numeric data, Journal of Intelligent Information Systems, v.26 n.2, p.185-207, March     2006
Andrzej Skowron , Piotr Synak, Reasoning in Information Maps, Fundamenta Informaticae, v.59 n.2-3, p.241-259, April 2004
Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, On compressing frequent patterns, Data & Knowledge Engineering, v.60 n.1, p.5-29, January, 2007
Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, ACM SIGMOD Record, v.29 n.2, p.1-12, June 2000
Jochen Hipp , Ulrich Gntzer , Gholamreza Nakhaeizadeh, Algorithms for association rule mining  a general survey and comparison, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.58-64, June, 2000
Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004
Jian Pei , Jiawei Han , Laks V. S. Lakshmanan, Pushing Convertible Constraints in Frequent Itemset Mining, Data Mining and Knowledge Discovery, v.8 n.3, p.227-252, May 2004
Aristides Gionis , Teija Kujala , Heikki Mannila, Fragments of order, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, Mining compressed frequent-pattern sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States
Gabriela Guimares , Lus Moniz Pereira, Inferring definite-clause grammars to express multivariate time series, Proceedings of the 18th international conference on Innovations in Applied Artificial Intelligence, p.332-341, June 22-24, 2005, Bari, Italy
Yves Bastide , Rafik Taouil , Nicolas Pasquier , Gerd Stumme , Lotfi Lakhal, Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.66-75, Dec. 2000
Yida Wang , Ee-Peng Lim , San-Yih Hwang, Efficient mining of group patterns from user movement data, Data & Knowledge Engineering, v.57 n.3, p.240-282, June 2006
Anthony K. H. Tung , Hongjun Lu , Jiawei Han , Ling Feng, Efficient Mining of Intertransaction Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.43-56, January
Tu-Bao Ho , Canh-Hao Nguyen , Saori Kawasaki , Si-Quang Le , Katsuhiko Takabayashi, Exploiting temporal relations in mining hepatitis data, New Generation Computing, v.25 n.3, p.247-262, January 2007
Chin-Chen Chang , Chih-Yang Lin , Henry Chou, Perfect hashing schemes for mining traversal patterns, Fundamenta Informaticae, v.70 n.3, p.185-202, April 2006
Ming-Yen Lin , Suh-Yin Lee, Incremental update on sequential patterns in large databases by implicit merging and efficient counting, Information Systems, v.29 n.5, p.385-404, July 2004
R. Anderson , Pedro Domingos , Daniel S. Weld, Personalizing web sites for mobile users, Proceedings of the 10th international conference on World Wide Web, p.565-575, May 01-05, 2001, Hong Kong, Hong Kong
Richard Relue , Xindong Wu , Hao Huang, Efficient runtime generation of association rules, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
Mohammad El-Ramly , Eleni Stroulia , Paul Sorenson, From run-time behavior to usage scenarios: an interaction-pattern mining approach, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Gregory Buehrer , Srinivasan Parthasarathy , Shirish Tatikonda , Tahsin Kurc , Joel Saltz, Toward terabyte pattern mining: an architecture-conscious solution, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, Complete Mining of Frequent Patterns from Graphs: Mining Graph Data, Machine Learning, v.50 n.3, p.321-354, March
Jiong Yang , Wei Wang , Philip S. Yu , Jiawei Han, Mining long sequential patterns in a noisy environment, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
Jun Wook Lee , Ok Hyun Paek , Keun Ho Ryu, Temporal moving pattern mining for location-based service, Journal of Systems and Software, v.73 n.3, p.481-490, November-December 2004
Carl H. Mooney , John F. Roddick, Marking time in sequence mining, Proceedings of the fifth Australasian conference on Data mining and analystics, p.129-134, November 29-30, 2006, Sydney, Australia
Wenke Lee , Salvatore J. Stolfo , Kui W. Mok, Algorithms for mining system audit data, Data mining, rough sets and granular computing, Physica-Verlag GmbH, Heidelberg, Germany, 2002
Jiong Yang , Wei Wang , Philip S. Yu, Mining Asynchronous Periodic Patterns in Time Series Data, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.613-628, March
Jian Pei , Jiawei Han, Constrained frequent pattern mining: a pattern-growth view, ACM SIGKDD Explorations Newsletter, v.4 n.1, June 2002
Jiawei Han , Jian Pei, Mining frequent patterns by pattern-growth: methodology and implications, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.14-20, Dec. 2000
Joo B.  D. Cabrera , Lundy Lewis , Xinzhou Qin , Wenke Lee , Raman K. Mehra, Proactive Intrusion Detection and Distributed Denial of Service AttacksA Case Study in Security Management, Journal of Network and Systems Management, v.10 n.2, p.225-254, June 2002
Tamas Abraham, Event sequence mining to develop profiles for computer forensic investigation purposes, Proceedings of the 2006 Australasian workshops on Grid computing and e-research, p.145-153, January 16-19, 2006, Hobart, Tasmania, Australia
Wei-Guang Teng , Ming-Syan Chen , Philip S. Yu, A regression-based temporal pattern mining scheme for data streams, Proceedings of the 29th international conference on Very large data bases, p.93-104, September 09-12, 2003, Berlin, Germany
Gerhard Widmer , Simon Dixon , Werner Goebl , Elias Pampalk , Asmir Tobudic, In search of the Horowitz factor, AI Magazine, v.24 n.3, p.111-130, September
Magnus Lie Hetland , Pl Strom, Evolutionary Rule Mining in Time Series Databases, Machine Learning, v.58 n.2-3, p.107-125, February  2005
Gosta Grahne , Jianfei Zhu, Fast Algorithms for Frequent Itemset Mining Using FP-Trees, IEEE Transactions on Knowledge and Data Engineering, v.17 n.10, p.1347-1362, October 2005
Theodore Johnson , Laks V. S. Lakshmanan , Raymond T. Ng, The 3W Model and Algebra for Unified Data Mining, Proceedings of the 26th International Conference on Very Large Data Bases, p.21-32, September 10-14, 2000
Jian Pei , Guozhu Dong , Wei Zou , Jiawei Han, Mining condensed frequent-pattern bases, Knowledge and Information Systems, v.6 n.5, p.570-594, September 2004
Gui-Rong Xue , Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma , Hong-Jiang Zhang , Chao-Jun Lu, Implicit link analysis for small web search, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
Yen-Liang Chen , Shih-Sheng Chen , Ping-Yu Hsu, Mining hybrid sequential patterns and sequential rules, Information Systems, v.27 n.5, p.345-362, July 2002
Mika Klemettinen , Heikki Mannila , Hannu Toivonen, Rule Discovery in Telecommunication AlarmData, Journal of Network and Systems Management, v.7 n.4, p.395-423, 7
Amol Ghoting , Gregory Buehrer , Srinivasan Parthasarathy , Daehyun Kim , Anthony Nguyen , Yen-Kuang Chen , Pradeep Dubey, Cache-conscious frequent pattern mining on a modern processor, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Yen-Liang Chen , Ya-Han Hu, Constraint-based sequential pattern mining: the consideration of recency and compactness, Decision Support Systems, v.42 n.2, p.1203-1215, November 2006
Shao-Shin Hung , Ting-Chia Kuo , Damon Shing-Min Liu, An Efficient Mining and Clustering Algorithm for Interactive Walk-Through Traversal Patterns, Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.356-362, September 20-24, 2004
Usama Fayyad, Knowledge discovery in databases: An overview, Relational Data Mining, Springer-Verlag New York, Inc., New York, NY, 2001
Yun Chi , Richard R. Muntz , Siegfried Nijssen , Joost N. Kok, Frequent Subtree Mining - An Overview, Fundamenta Informaticae, v.66 n.1-2, p.161-198, January 2005
E. Boros , V. Gurvich , L. Khachiyan , K. Makino, On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices, Annals of Mathematics and Artificial Intelligence, v.39 n.3, p.211-221, November
Alexandros Nanopoulos , Dimitrios Katsaros , Yannis Manolopoulos, A Data Mining Algorithm for Generalized Web Prefetching, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1155-1169, September
Taneli Mielikinen , Evimaria Terzi , Panayiotis Tsaparas, Aggregating time partitions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
van der Aalst , Ton Weijters , Laura Maruster, Workflow Mining: Discovering Process Models from Event Logs, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1128-1142, September 2004
Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997
Jiong Yang , Wei Wang , Philip S. Yu, Mining Surprising Periodic Patterns, Data Mining and Knowledge Discovery, v.9 n.2, p.189-216, September 2004
Amol Ghoting , Gregory Buehrer , Srinivasan Parthasarathy , Daehyun Kim , Anthony Nguyen , Yen-Kuang Chen , Pradeep Dubey, Cache-conscious frequent pattern mining on modern and emerging processors, The VLDB Journal  The International Journal on Very Large Data Bases, v.16 n.1, p.77-96, January 2007
Zhiping Zeng , Jianyong Wang , Lizhu Zhou , George Karypis, Out-of-core coherent closed quasi-clique mining from large dense graph databases, ACM Transactions on Database Systems (TODS), v.32 n.2, p.13-es, June 2007
David Al-Dabass , Evtim Peytchev , Mohamed Khalil , Manling Ren, Scalability issues in urban traffic systems, Proceedings of the 1st international conference on Scalable information systems, p.31-es, May 30-June 01, 2006, Hong Kong
Klaus Julisch , Marc Dacier, Mining intrusion detection alarms for actionable knowledge, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
W. M. P. van der Aalst , A. J. M. M. Weijters, Process mining: a research agenda, Computers in Industry, v.53 n.3, p.231-244, April 2004
Ling Feng , Jeffrey Xu Yu , Hongjun Lu , Jiawei Han, A template model for multidimensional inter-transactional association rules, The VLDB Journal  The International Journal on Very Large Data Bases, v.11 n.2, p.153-175, October 2002
Qing Li , Ling Feng , Allan Wong, From intra-transaction to generalized inter-transaction: landscaping multidimensional contexts in association rule mining, Information SciencesInformatics and Computer Science: An International Journal, v.172 n.3-4, p.361-395, 9 June 2005
Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999
Taneli Mielikinen, Frequency-based views to pattern collections, Discrete Applied Mathematics, v.154 n.7, p.1113-1139, 1 May 2006
Jos L. Balczar , Gemma C. Garriga, Horn axiomatizations for sequential data, Theoretical Computer Science, v.371 n.3, p.247-264, March, 2007
Xingquan Zhu , Xindong Wu , Ahmed K. Elmagarmid , Zhe Feng , Lide Wu, Video Data Mining: Semantic Indexing and Event Detection from the Association Perspective, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.665-677, May 2005
Jiawei Han , Laks V. S. Lakshmanan , Jian Pei, Scalable frequent-pattern mining methods: an overview, Tutorial notes of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, August 26-29, 2001, San Francisco, California
Vipin Kumar , Mohammed Zaki, High performance data mining (tutorial PM-3), Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.309-425, August 20-23, 2000, Boston, Massachusetts, United States
frequent episodes;event sequences;sequence analysis