
Algorithm 1 **Unified Algorithm for counting serial episodes**

Input: Set CN of N**-node serial episodes, event stream** D =

h(E1, t1), . . ., (En, tn))i,

Output: **Frequencies of episodes in** CN

1: for all α ∈ CN do

2: Add automaton of α **waiting in the start state.**

3: Initialize frequency of α **to ZERO.**

4: for l **= 1 to** n do 5: for each automaton, A**, ready to accept event-type** Ei

do

6: α**=candidate associated with** A;

7: j = state which A **is ready to transit into;**

8: if TRANSIT **then** 9: if COPYAUTOMATON **then**

10: Add Copy of A **to collection of automata.**

11: Transit A **to state** j

12: if ∃ an earlier automaton of α **already in state** j

but not waiting for Ei **then**

13: if JOIN-AUTOMATON **then**

14: Retain A **and retire earlier automaton**

15: if A reached final state **then**

16: Retire A.

17: if INCREMENT-FREQ **then**

18: Increment frequency of α **by INC.**

19: if RETIRE-AUTOMATON **then**

20: Retire all automaton of α **and create a**

state '0' automaton.

occurrences of not only α **but also of all its subepisodes in**
D**. Hence the third inequality is also true. Also, it is easy**
to verify that a set of non-interleaved occurrences of an injective episode are also distinct, which validates the fourth inequality. We will show the correctness of the remaining two inequalities in the next section.

## 4. Proofs Of Correctness

In this section, we present proofs of correctness of the different frequency counting algorithms presented in Sec. 3 (all of which are specific instances of **Algorithm 1**).

In our proofs, we consider the case of event sequences with distinct occurrence-times for events. When we are not considering expiry-time constraints, the actual values of times of occurrences of different events are not really important; only the time ordering of the events is important in deciding on the occurrences of episodes. Hence, in this section we will use h(v1) interchangeably with th(v1)**, the time of the first**
event in the occurrence h **and so on. Modifications needed**
in the case of data having multiple events with the same time of occurrence, are discussed at the end of the section.

## 4.1 Minimal Window Counting Algorithm

First, we analyze the minimal occurrences counting algorithm (MO). Our proof methodology is different from the one presented in [4], where, the algorithm is viewed as computing a table S[0 . . . n, 0 . . . N], where, S[i, j**] is the largest**
value k ≤ i such that Ek . . . Ei **contains an occurrence of**
α[1] → . . . α[j], using dynamic programming. The algorithm, after processing Ei**, stores the** i th **row of this matrix. The dynamic programming recursion helps compute**
the i th row of this matrix from its (i − 1)th **row. Whenever**
S[i, N] > S[i − 1, N**], the count is incremented since a new**
minimal occurrence is recognized. Viewed from an automata perspective, the i th **row of the matrix essentially stores the**
first state transition times of the currently active automata. Our analysis of the minimal occurrence algorithm also leads to an analysis and proof for counting non-overlapped occurrences (NO and NO-X) as well. Another advantage of our proof strategy is that it may be generalized to the case of episodes with general partial orders. (We briefly discuss this in section 6).

Lemma 1. Suppose h **is an earliest transiting occurrence**
of an N-node episode α**. If** h
′**is any general occurrence such**
that h <⋆ h
′**, then** h(vi) ≤ h
′(vi) ∀i = 1, 2**, . . . N**.

This lemma follows easily from the definition of the lexicographic ordering, <⋆**, and the definition of earliest transiting**
occurrence.

Remark 3. **Recall that** h e i**is the** i th **earliest transiting**
(ET) occurrence of an episode. Thus, by definition, h e i (v1) <
h e j (v1) and h e i <⋆ h e j whenever i < j**. Hence, from the**
above lemma, we have h e i (vk) ≤ h e j (vk) for all k and **i < j**.

In particular, we have, h e i (v1) < he i+1(v1) and h e i (vN ) ≤
h e i+1(vN ), for an N**-node episode.**
The main idea of our proof is that to find all minimal windows of an episode, it is enough to capture a certain subset of earliest transiting occurrences.

Lemma 2. **An earliest transiting (ET) occurrence** h e i**, of**
an N**-node episode, is not a minimal occurrence if and only**
if h e i (vN ) = h e i+1(vN ).

Proof. **The 'if' part follows easily from Remark 3. For**
the 'only if' part, let us denote by w = [ns, ne**] = [**h e i (v1), he i (vN )]
the window of h e i. Given that w **is not a minimal window,**
we need to show that h e i (vN ) = h e i+1(vN ). Since w **is not a**
minimal window, one of its proper sub-windows contains an occurrence, say, h, of this episode. That means if h **starts at**
ns then it must end before ne**. But, since** h e i**is earliest transiting, any occurrence starting at the same event as** h e i can not end before h e i. Thus we must have h(v1) > he i (v1**). This**
means, by lemma 1, since h e i**is earliest transiting, we can not**
have h e i (vN ) > h(vN ). Since the window of h **has to be contained in the window of** h e i**, we thus have** h e i (vN ) = h(vN ).

By definition, h e i+1 **will start at the earliest possible position after** h e i**. Since there is an occurrence starting with**
h(v1**) we must have** h e i+1(v1) ≤ h(v1**). Now, since** h e i+1 is earliest transiting, it can not end after h**. Thus we must**
have h e i+1(vN ) ≤ h(vN **). Also,** h e i+1 **can not end earlier than**
h e i **because both are earliest transiting. Thus, we must have**
h e i (vN ) = h e i+1(vN **). This completes proof of lemma.**
Remark 4. **This lemma shows that any ET occurrence**
h e i **such that** h e i (vN ) < he i+1(vN ) **is a minimal occurrence.**
The converse is also true. Consider a minimal window w =
[ns, ne]. Since this is a minimal window, there is an occurrence (and hence an ET occurrence) starting at ns**. Denote**
this ET occurrence by h e i**. We know** h e i (vN ) = ne **because**
w **is a minimal window. Then the next ET occurrence** h e i+1 has to start after ns and has to end beyond ne **because** w is minimal. Thus we have h e i (vN ) < he i+1(vN ).

Now we are ready to prove correctness of the MO algorithm.

Consider Algorithm 1 operating in the MO(minimal occurrence) mode for tracking occurrences of an N-node episode