algorithms.

Apart from the five boolean variables explained above, our general algorithm contains one more variable, namely, INC,
which decides the amount by which frequency is incremented when an automaton reaches the final state. Its values for different frequency counts are listed in Table 7. For all algorithms except WB, we set INC **= 1. We now explain how frequency is incremented in WB. To count the**
number of sliding windows that contain at least one occurrence of the episode, whenever a new minimal occurrence enters a sliding window, we can calculate the number of consecutive windows in which this new minimal occurrence will be found in. For example, in D1, with a windowwidth of TX **= 16, consider the first minimal occurrence of**
(A → B → C → D**), namely, the occurrence constituted by** events (A, 5), (B, 9), (C, 11) and (D, **15). The first sliding** window in which this occurrence can be found is [−1, **15].**
The occurrence stays in consecutive sliding windows, until the sliding window [5, 21]. When this first minimal occurrence enters the sliding window [−1, **15], we observe that**
there is no other 'older' minimal occurrence in [−1, **15], and**
hence, as per the else condition in Table 7, the INC is incremented by (5−(−**1)+ 1) = 7. Similarly, when the second**
minimal occurrence enters the sliding window [7, 23], we increment INC by (14 − 7 + 1 = 8). The third minimal occurrence (constituted by the events (A, 22), (B, 24), (C, 25)
and (D, 29)) first enters the sliding window [13, **29], with the**
second minimal window still occurring within this window.

This third minimal occurrence remains in consecutive sliding windows until [22, 38]. As per the if condition of **Table**
7, INC is incremented by 22 − **14 = 8. We note that such**
an implementation of the windows-based algorithm removes the need for the beginsat(t**) list of [14] which was used to**
store all automata whose first state transition occurred at time-tick t.

Remark 1. **Even though we included AO (for counting**
all occurrences of an episode) for sake of completeness, this is not a good frequency measure. This is mainly because it does not seem to satisfy any anti-monotonicity condition.

For example, consider the data sequence **< AABBCC >**.

There are 8 occurrences of (A → B → C) but only 4 occurrences of each of its 2**-node subepisodes. Also, its space**
complexity can be high.

Remark 2. **: The quantitative relationships between the**
different frequency counts for a given episode can be described as follows:

$f_{all}\geq f_h\geq f_{tot}\geq f_d\geq f_{ni}\geq f_{mi}\geq f_{no}$. 
where fall **denotes the frequency of an episode under AO,**
while fh and ftot **denote the corresponding head and total**
frequencies defined with a window-width exceeding the total time-span of the event sequence. For a large sliding window width, the head frequency fh **is same as the number of**
earliest transiting occurrences of an episode. In general, the inequality fd ≥ fni **holds only for injective episodes (An**
episode α **is injective if it does not contain any repeated**
event-types). All other inequalities are true for any serial episode. The first inequality is obvious. The second inequality follows directly from equation 2 in definition 4**. Given a**
set of f maximal distinct occurrences of an episode α **in a**
data stream D**, one can extract that many earliest transiting**

| Table 1: Various frequency counts   |                                                 |
|-------------------------------------|-------------------------------------------------|
| WB                                  | Windows based                                   |
| MO                                  | Minimal Occurrences based                       |
| MO-X                                | Minimal Occurrence with Expiry time constraints |
| NO                                  | Non-overlapped                                  |
| NO-I                                | Non-overlapped innermost                        |
| NO-X                                | Non-overlapped with Expiry time constraints     |
| NI                                  | Non-interleaved                                 |
| DO                                  | Distinct occurrences based                      |
| AO                                  | All occurrences based                           |
| HD                                  | Head frequency                                  |

Table 2: Conditions for TRANSIT=TRUE

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

![0_image_2.png](0_image_2.png)

![0_image_3.png](0_image_3.png)

![0_image_4.png](0_image_4.png)

![0_image_5.png](0_image_5.png)

INC = 1 for all counts except WB. For Windows Based count(WB),
If(first window which contains current minimal occurrence also contains the previous minimal occurrence), then INC = Time diff. between start of last window containing the current minimal occurrence and the start of last window which contains previous minimal occurrence. else INC=time difference between the first and last window containing the current occurrence +1.