
## 2. An Overview Of Frequent Episode Discovery

In this section we briefly review the framework of frequent episode discovery [14]. The data, referred to as an **event**
sequence, is denoted by D = h(E1, t1), (E2, t2), . . .(En, tn)i, where each pair (Ei, ti) represents an event**, and the number**
of events in the event sequence is n. Each Ei **is a symbol** (or event-type) from a finite alphabet, E, and ti **is a positive**
integer representing the time of occurrence of the i th **event.**
The sequence is ordered so that, ti ≤ ti+1 for all i = 1, 2**, . . .**.

The following is an example event sequence with 10 events:
(A, 1),(A, 2),(B, 3),(A, 6),(A, 7),(C, 8),(B, 9),(D, 11),
(C, 12),(A, 13),(B, 14),(C, **15) (1)**
An N-node episode, α, is defined as a triple, (Vα, ≤α, gα),
where Vα = {v1, v2, . . . vN }, is a collection of N **nodes,** ≤α is a partial order on Vα and gα : Vα → E **is a map that** associates each node in α with an event type from E**. Thus**
an episode is a (typically small) collection of event-types along with an associated partial order. When the order ≤α is total, α **is called a serial episode, and when the order**
is empty, α **is called a parallel episode. In this paper, we**
restrict our attention to serial episodes1**. Without loss of**
generality, we can now assume that the total order on the nodes of α is given by v1 ≤α v2 ≤α . . . ≤α vN **. For example,**
consider a 3-node episode Vα = {v1, v2, v3}, gα(v1) = A,
gα(v2) = B, gα(v3) = C, with v1 ≤α v2 ≤α v3**. We denote**
such an episode by (A → B → C**). An occurrence of episode**
α in an event sequence D is a map h : Vα → {1, . . . , n} **such**
that gα(v) = Eh(v)for all v ∈ Vα, and for all **v, w** ∈ Vα with v <α w we have th(v) < th(w)**. In the example event**
sequence (1), the events (A, 2), (B, 3) and (C, **8) constitute**
an occurrence of (A → B → C) while (B, 3), (A, **7) and**
(C, 8) do not. We use α[i**] to refer to the** i th **event-type in**
α. This way, an N-node episode α **can be represented using**
(α[1] → α[2] → . . . → α[N]). An episode β **is said to be**
a subepisode of α (denoted β  α**) if all the event-types in** β also appear in α, and if their order in β **is same as that** in α. For example, (A → C**) is a 2-node subepisode of the** episode (A → B → C) while (B → A**) is not.**
The frequency **of an episode is some measure of how often**
it occurs in the event sequence. A frequent episode is one whose frequency exceeds a user-defined threshold. The task in frequent episode discovery is to find all frequent episodes.

Given an occurrence h of an N-node episode α, (th(vN ) −
th(v1)) is called the span **of the occurrence. In many applications, one may want to consider only those occurrences**
whose span is below some user-chosen limit. (This is because, occurrences constituted by events that are widely separated in time may not represent any underlying causative influences). We call any such constraint on span as an expiry-time constraint. The constraint is specified by a threshold, TX**, such that occurrences of episodes whose span is**
greater than TX **are not considered while counting the frequency.**
One popular approach to frequent episode discovery is to use an Apriori-style level-wise procedure. At level k **of the**
procedure, a 'candidate generation' step combines frequent episodes of size (k − 1) to build candidates (or potential frequent episodes) of size k **using some kind of anti-monotonicity**
1**From now on, we will simply use 'episode' to refer to a**
serial episode.

property (e.g. frequency of an episode cannot exceed frequency of any of its subepisodes). The second step at level k is called 'frequency counting' in which, the algorithm counts or computes the frequencies of the candidates and determines which of them are frequent.

## 2.1 Frequencies Of Episodes

There are many ways to define the frequency of an episode. Intuitively, any definition must capture some notion of how often the episode occurs in the data. It must also admit an efficient algorithm to obtain the frequencies for a set of episodes. Further, to be able to apply a level-wise procedure, we need the frequency definition to satisfy some antimonotonicity criterion. Additionally, we would also like the frequency definition to be conducive to statistical significance analysis.

In this section, we discuss various frequency definitions that have been proposed in literature. (Recall that the data is an event sequence, D = h(E1, t1), . . .(En, tn)i).

Definition 1. **[14] A window on an event sequence,** D,
is a time interval [ts, te], where ts and te **are positive integers**
such that ts ≤ tn and te ≥ t1. The window width of [ts, te]
is given by (te − ts)**. Given a user-defined window width**
TX, the windows-based frequency of α **is the number of**
windows of width TX **which contain at least one occurrence**
of α.

For example, in the event sequence (1), there are 5 windows with window width 5 which contain an occurrence of (A →
B → C).

Definition 2. **[14] The time-window of an occurrence,**
h, of α is given by [th(v1), th(vN )]. A **minimal window** of α is a time-window which contains an occurrence of α**, such**
that no proper sub-window of it contains an occurrence of α**. An occurrence in a minimal window is called a minimal**
occurrence. The **minimal occurrences-based frequency**
of α in D (denoted fmi**) is defined as the number of minimal**
windows of α in D.

In the example sequence (1) there are 3 minimal windows of
(A → B → C): [2, 8], [7, 12] and [13, **15].**
Definition 3. [7] Given a window-width k, the **head**
frequency of α is the number of windows of width k **which**
contain an occurrence of α **starting at the left-end of the**
window and is denoted as fh(**α, k**).

Definition 4. [7] Given a window width k, the **total**
frequency of α, denoted as ftot(α, k)**, is defined as follows.**
$$\begin{array}{r c l}{{f_{t o t}(\alpha,k)}}&{{=}}&{{\operatorname*{min}_{\beta\preceq\alpha}f_{h}(\beta,k)}}\end{array}$$
$\left(2\right)$. 
fh(β, k**) (2)**
For a window-width of 6, the head frequency fh(γ, **6) of**
γ = (A → B → C**) in (1) is 4. The total frequency of** γ, ftot(γ, k**), in (1) is 3 because the head frequency of (**B → C)
in (1) is 3.

Definition 5. [9] Two occurrences h1 and h2 of α are said to be non-overlapped if either th1(vN ) < th2(v1) or th2(vN ) <
th1(v1)**. A set of occurrences is said to be non-overlapped if**
every pair of occurrences in the set is non-overlapped. A