$\pi_{1}=\operatorname{\pi_{\vbox{\hbox{\scalebox{0.5}{$\swarrow$}}}}}(\texttt{n})$
and, for every $i\leq m$,
$\pi_{i}=\pi_{i-1}^{u}\cdot\operatorname{\pi_{\vbox{\hbox{\scalebox{0.5}{$\swarrow$}}}}}(\textsf{right}(\texttt{u}))$,
where u is the last node of $\pi_{i-1}^{u}$. In other words, it performs a
greedy DFS from left to right: the first path to enumerate is
$\pi_{1}=\operatorname{\pi_{\vbox{\hbox{\scalebox{0.5}{$\swarrow$}}}}}(\texttt{n})$,
then each $\pi_{i}$ is the path of
$\operatorname{paths}_{\geq\tau}(\texttt{n})$ that branches from $\pi_{i-1}$
to the right at the deepest level (u) and from there follows the leftmost
path. Moreover, to jump from $\pi_{i-1}$ to $\pi_{i}$, the node popped by the
stack is exactly u, that is, the last node of $\pi_{i-1}^{u}$.

To show that the enumeration is done with output-linear delay, we study how
long it takes between enumerating the complex events of $\pi_{i-1}$ and
$\pi_{i}$. Consider that $\pi_{i-1}$ was just traversed and its complex event
was output by line 9. Then, the break of line 10 is executed, breaking the
while of line 7. Afterwards, either the stack is empty and the algorithm ends,
or a pair $(\texttt{m},R)$ is popped from the stack, where m corresponds to
the last node of $\pi_{i-1}^{u}$. From that point, it is straightforward to
see that the number of iterations of the while of line 7 (each taking constant
time) is equal to the number of nodes $l$ in
$\operatorname{\pi_{\vbox{\hbox{\scalebox{0.5}{$\swarrow$}}}}}(\texttt{m})$,
so those nodes are traversed and the complex event of the path $\pi_{i}$ is
output. But, because $\mathcal{E}$ is $k$-bounded, then $l\leq k\cdot|O|$,
where $O$ is the complex event of $\pi_{i}$. Finally, the time taken is
bounded by the size of the output, and the enumeration is performed with
output-linear delay. ∎

By Lemmas 1 and 2, Theorem 3 immediately holds. ∎

###  B.2. Proof of Theorem 4

See 4

###### Proof.

Fix a CEA $\mathcal{A}=(Q,\Delta,q_{0},F)$ and a stream $S=t_{0}t_{2}\ldots$.
Given a run of $\mathcal{A}$ over $S$ of the form
$\rho:=q_{i}\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P_{i}/m_{i}}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}q_{i+1}\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P_{i+1}/m_{i+1}}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}\ldots\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P_{j}/m_{j}}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}q_{j+1}$,
let $o(\rho)=(i,D)$ where $D=\\{k\mid i\leq k\leq j\land m_{k}=\bullet\\}$ be
the open complex event associated to $\rho$. For any position $j$ and a state
$q\in Q$, let $R_{j}^{q}$ be the set of runs that reach $q$ after reading
position $j$ of the stream, that is, $R_{j}^{q}=\\{\rho\mid\exists
i.\,\text{$\rho$ is a run of $\mathcal{A}$ over $S$ from positions $i$ to
$j$}\\}$. Further, let $CE_{j}^{q}=\\{o(\rho)\mid\rho\in R_{j}^{q}\\}$ be the
set of corresponding open complex events.

For a union-list
$\texttt{ul}=\texttt{n}_{0},\texttt{n}_{1},\ldots,\texttt{n}_{k}$, of a tECD
$\mathcal{E}$ define its set of open complex events as expected:
$o(\texttt{ul})={\llbracket{}{\texttt{n}_{0}}\rrbracket}_{\mathcal{E}}\cup\ldots\cup{\llbracket{}{\texttt{n}_{k}}\rrbracket}_{\mathcal{E}}$.
Then, for a position $j$ and a state $q\in Q$ let
$ACE_{j}^{q}=o(\operatorname{T}[q])$ be the set of open complex events stored
by $\operatorname{T}[q]$ after reading position $j$ of the stream, i.e., after
the $(j+1)$-th iteration of the while of line 4 of Algorithm 1.

Note that
${\llbracket{}{\mathcal{A}}\rrbracket}^{\epsilon}_{j}(S)=\\{([i,j],D)\mid(i,D)\in\bigcup_{q\in
F}CE_{j}^{q}\land j-i\leq\epsilon\\}$. One can see that in Algorithm 1, if
after the $j$-th iteration the underlying tECS $\mathcal{E}$ is time-ordered
and $k$-bounded for some constant $k$ and all nodes of $\mathcal{E}$ are
duplicate-free, then by Theorem 3 procedure Output enumerates the set
$\\{([i,j],D)\mid(i,D)\in\bigcup_{q\in F}ACE_{j}^{q}\land j-i\leq\epsilon\\}$
with output-linear delay. Therefore, if we prove that, for every $j$ and $q$,
(1) $CE_{j}^{q}=ACE_{j}^{q}$, (2) $\mathcal{E}$ is time-ordered and
$k$-bounded and (3) all nodes in $\mathcal{E}$ are duplicate-free, then the
theorem holds.

Before we start proving (1)-(3), let us first analyse procedure ExecTrans. At
the beginning of iteration $j$, every $ACE^{q}_{j}$ starts empty. Then, every
time $\textsc{ExecTrans}(p,\texttt{ul},t,j)$ is called, it takes all open
complex events in $ACE^{p}_{j-1}$ and:

  * •

for $q_{\circ}=\Delta(p,t,\circ)$, it makes $ACE^{q_{\circ}}_{j}\leftarrow
ACE^{q_{\circ}}_{j}\cup ACE^{p}_{j-1}$; and

  * •

for $q_{\bullet}=\Delta(p,t,\bullet)$, it makes
$ACE^{q_{\bullet}}_{j}\leftarrow
ACE^{q_{\bullet}}_{j}\cup(ACE^{p}_{j-1}\times\\{j\\})$, where
$ACE^{p}_{j-1}\times\\{j\\}=\\{(i,D\cup\\{j\\})\mid(i,D)\in ACE^{p}_{j-1}\\}$.

The two cases in Add just handle whether $ACE^{q_{\bullet}}_{j}$ or
$ACE^{q_{\circ}}_{j}$ are empty at the moment or not.

We will prove (1) by simple induction over $j$. For the base case, consider
the state before the first iteration, namely $j=-1$ and
$\operatorname{T}=\emptyset$. It is easy to see that
$CE_{-1}^{q}=ACE_{-1}^{q}=\emptyset$, so the property holds. Now for the
inductive case, consider that $CE_{j}^{q}=ACE_{j}^{q}$. First, a new list with
only a bottom node is created and stored in ul and then
$\textsc{ExecTrans}(q_{0},\texttt{ul},t,j)$ is called. This starts possibly
two runs from the initial state $q_{0}$ with either a $\circ$ or
$\bullet$-transition. Then,
$\textsc{ExecTrans}(q_{0},\operatorname{T}[p],t,j)$ is called for every state
that is active before reading position $j$, i.e., for every $p$ with
$ACE_{j}^{p}\neq\emptyset$. Let us consider any $(i,D)\in ACE_{j+1}^{q}$. If
it came from the first call to ExecTrans, then it means that $i=j$ and, either
$D=\\{j\\}$ and there is a run (from $j+1$ to $j+1$) of the form
$\rho=q_{0}\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P/\bullet}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}q$,
or $D=\emptyset$ and there is a run (from $j+1$ to $j+1$)
$\rho=q_{0}\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P/\circ}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}q$.
Either way, the corresponding run assures that $(i,D)\in CE_{j+1}^{q}$. Now,
if $(i,D)$ came from one of the subsequent calls to ExecTrans, it means that
there was some $(i,D^{\prime})\in ACE_{j}^{p}$ such that either $D=D^{\prime}$
and $q=\Delta(p,t_{j},\circ)$, or $D=D^{\prime}\cup\\{j\\}$ and
$q=\Delta(p,t_{j},\bullet)$. Call such transition $e$. By induction
hypothesis, there is a run from $i$ to $j$
$\rho=q_{i}\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P_{i}/m_{i}}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}q_{i+1}\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P_{i+1}/m_{i+1}}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}\ldots\raisebox{-1.0pt}[10.0pt][0.0pt]{$\overset{P_{j}/m_{j}}{\underset{}{\raisebox{0.0pt}[3.0pt][0.0pt]{$\relbar\mspace{-8.0mu}\longrightarrow$}}}$}p$
with $o(\rho)=(i,D^{\prime})$. Therefore, there is a run $\rho^{\prime}$ that
extends $\rho$ with $e$ such that $o(\rho^{\prime})=(i,D)$ and
$\rho^{\prime}\in R^{q}_{j+1}$, therefore $(i,D)\in ACE^{q}_{j+1}$. Then,
$CE^{q}_{j+1}\subseteq ACE^{q}_{j+1}$. We can use the same analysis to prove
that $ACE^{q}_{j+1}\subseteq CE^{q}_{j+1}$, thus $CE^{q}_{j+1}=ACE^{q}_{j+1}$
and the induction holds.

Now, we focus on proving (2). It has already been shown that every operation
over tECS $\mathcal{E}$ used by Algorithm 1 preserves the time-ordered and
$k$-boundedness for $k=3$, provided that every time we call
$\textsf{union}(\texttt{n}_{1},\texttt{n}_{2})$, both $\texttt{n}_{1}$ and
$\texttt{n}_{2}$ are safe nodes. In particular, since we only manage unions
using union-lists, we only need to check that every time $\textsf{new-
ulist}(\texttt{n})$ or $\textsf{insert}(\texttt{ul},\texttt{n})$ are called,
the input node n is a safe one. This is easily verifiably by looking at lines
7, 17 and 24 of Algorithm 1 (for 17 and 24, recall that
$\textsf{merge}(\texttt{ul})$ returns a safe node). Note that
$\textsf{merge}(\texttt{ul})$ does not have any requirement, since its correct
behaviour is ensured by using the other operations correctly. Therefore, at
any moment in the evaluation, the underlying tECS $\mathcal{E}$ is time-
ordered and 3-bounded. Note that $\textsf{insert}(\texttt{ul},\texttt{n})$ has
another precondition: that
$\text{max}(\texttt{n}_{0})\geq\text{max}(\texttt{n})$, where $\texttt{n}_{0}$
is the first node of ul. Since this does not relate directly with the
correctness of the output of Algorithm 1, but with an overall correct
behaviour of the algorithm, this property is discussed in the next section,
along with another property that is needed to ensure constant update-time.

Next, we prove (3). By taking a look at Algorithm 1, one can see that the only
ways it could add to $\mathcal{E}$ nodes with duplicates are with methods
merge and insert, particularly in lines 14, 24 and 32. Fix a position $j$. Let
$\operatorname{All-N}$ be the set all nodes in the union-list of some state at
position $j$, i.e., $\operatorname{All-N}=\\{\texttt{n}\mid\exists q.\exists
i.T[q]=\texttt{n}_{0},\ldots,\texttt{n}_{l}\land\texttt{n}_{i}=\texttt{n}\\}$,
where $T[q]$ is its value at iteration $j$. If, for every two
$\texttt{n}_{1},\texttt{n}_{2}\in\operatorname{All-N}$ with
$\texttt{n}_{1}\neq\texttt{n}_{2}$ it holds that
${\llbracket{}{\texttt{n}_{i}}\rrbracket}_{\mathcal{E}}\cap{\llbracket{}{\texttt{n}_{j}}\rrbracket}_{\mathcal{E}}=\emptyset$,
then all cases are solved and the algorithm creates no nodes with duplicates.
One can see that each ${\llbracket{}{\texttt{n}}\rrbracket}_{\mathcal{E}}$
actually stores the open complex events for a disjoint set of runs. Then, if
there were some $\texttt{n}_{1},\texttt{n}_{2}\in\operatorname{All-N}$ with
${\llbracket{}{\texttt{n}_{1}}\rrbracket}_{\mathcal{E}}\cap{\llbracket{}{\texttt{n}_{2}}\rrbracket}_{\mathcal{E}}\neq\emptyset$,
it would mean that there are two different runs defining the same output, thus
contradicting the fact that $\mathcal{A}$ is I/O-deterministic. Therefore, all
nodes must define disjoint sets and Algorithm 1 only adds duplicate-free nodes
to $\mathcal{E}$.

Finally, because (1)-(3) hold, also does the theorem. ∎

###  B.3. Special invariants of union-lists in Algorithm 1

In this section we discuss in more detail two invariants maintained by
Algorithm 1 which are needed for its correct behaviour. Specifically, we prove
that:

  1. (1)

every time a node n is added to some union-list
$\texttt{ul}=\texttt{n}_{0},\ldots,\texttt{n}_{k}$, it is the case that
$\text{max}(\texttt{n}_{0})\geq\text{max}(\texttt{n})$; and

  2. (2)

at any moment, the length of every union-list $\operatorname{T}[q]$ is smaller
than the number of states of the automaton $\mathcal{A}$.

The former assures that the first node $\texttt{n}_{0}$ always remains a non-
union node, while the latter is needed so that operations merge and insert
take constant time (when $\mathcal{A}$ is fixed).

First, we focus on (1). This comes directly from the order in which we update
the union-lists. As notation, for a non-empty union-list
$\texttt{ul}=\texttt{n}_{0},\ldots,\texttt{n}_{k}$, we write
$\text{max}(\texttt{ul})=\text{max}(\texttt{n}_{0})$. Consider any iteration
$j\geq 0$ and let $q_{1},\ldots,q_{l}$ be the order given by $\textsf{ordered-
keys}(\operatorname{T})$. One can prove that this order actually preserves the
following property:
$\text{max}(\operatorname{T}[q_{i}])\geq\text{max}(\operatorname{T}[q_{i+1}])$
for every $i<l$. One can prove this by simple induction over $j$. As
consequence, if $\textsc{ExecTrans}(q_{i},\operatorname{T}[q_{i}],t,j)$ is
called and we need to add some node n at some union-list ul, it must be that
ul was the result of some previous call
$\textsc{ExecTrans}(q_{k},\operatorname{T}[q_{k}],t,j)$ with $k<i$, and so
$\text{max}(\texttt{ul})\geq\text{max}(\operatorname{T}[q_{k}])\geq\text{max}(\texttt{n})$.

Now we prove (2). First, we show a property about the possible maximum-start
values at any iteration of the algorithm. For $j\geq 0$, we define the set of
maximum-starts at iteration $j$ as
$M_{j}=\\{\text{max}(\operatorname{T}[q])\mid
q\in\textsf{keys}(\operatorname{T})\\}$. The property we use is that the set
$M_{j}$ is closely restricted by the set $M_{j-1}$ of the previous iteration.
Specifically, one can see that $M_{j}$ must always be a subset of $M_{j-1}$,
with the possibility of adding the maximum-start $j$ if a new run begins at
that iteration, i.e., $M_{j}\subseteq(M_{j-1}\cup\\{j\\})$. This is because
the maximum-start of every union-list $\operatorname{T}[q]$ at some iteration
came either from extending the already existing runs of the previous
iteration, therefore maintaining its maximum-start, or from starting a new run
with maximum-start $j$.

Consider any union-list $\operatorname{T}[q]$ created at iteration $j$. From
(1), we know that we will only add to $\operatorname{T}[q]$ nodes n with
$\text{max}(\texttt{n})\leq\text{max}(\operatorname{T}[q])$. Moreover, it is
always the case that $\text{max}(\texttt{n})\in M_{j}$. This is clear for
iteration $j$, but it actually holds for the following ones. Indeed,
$\operatorname{T}[q]$ could actually receive insertions in some future
iteration, call it $k$. However, since $\text{max}(\operatorname{T}[q])$ does
not change and the new maximum-start values in $M_{k}$ are higher than
$j\geq\text{max}(\operatorname{T}[q])$, the actual maximum-start values that
could be added to $\operatorname{T}[q]$ are still in $M_{j}\cap M_{k}\subseteq
M_{j}$. Therefore, the size of $\operatorname{T}[q]$ is bounded by
$|M_{j}|\leq|Q|$.

##  Appendix C Other baseline systems

We have surveyed the literature for other systems to compare against, but have
chosen to limit our experiments to SASE (Wu et al., 2006), Esper (Esp,
[n.d.]), FlinkCEP (Fli, [n.d.]), and OpenCEP (Ope, [n.d.]), for the following
reasons.

First, we cannot compare against systems that, while published in the
literature, do not publish an accompanying implementation (e.g., ZStream (Mei
and Madden, 2009), NextCEP (Schultz-Møller et al., 2009), DistCED (Pietzuch et
al., 2003), SAP ESP (Zhang et al., 2017)666SAP offers 30-day trial versions of
its products, however, SAP ESP itself is no longer available from its
website.) or whose implementation was discontinued in the last decade (e.g.,
Cayuga (Demers et al., 2006)). Second, we cannot compare against proposals
that do not offer a CER query language or whose implementation does not allow
running the queries considered here (e.g. CET (Poppe et al., 2017a), GRETA
(Poppe et al., 2017b)). We do not consider comparison against system whose
optimization focus is on additional CER features (Zhao et al., 2021; Hirzel,
2012; Zhao et al., 2020), such as load shedding (Zhao et al., 2020) or
interacting with external, non-stream data sources (Zhao et al., 2021), for
which the comparison would not be fair. Finally, we do not compare against
streaming SQL systems like Spark and Flink SQL whose SQL-based query languages
do not natively support basic CER operators, like sequencing and iteration.

We _have_ run experiments to compare against TESLA/TRex (Cugola and Margara,
2010, 2012a) and Siddhi (Suhothayan et al., 2011; Sid, [n.d.]). Unfortunately,
their event recognition features differ from CORE’s; in particular, they do
not have dedicated support for count-based time windows.777Although Siddhi has
an operator for time windows, on can only use it in the presence of
aggregation. As such, one cannot retrieve the complex events found, only
aggregations thereof. As such, they are not optimized for the use cases that
we aim to test here. When we expressed simple sequence queries with time
windows by means of other features in their query languages (e.g., by using
inequality predicates), performance was so limited (i.e., a throughput of less
than ten events per second), that we decided not to further report the results
of TESLA/TRex and Siddhi.

##  Appendix D Stock market dataset

Dataset. We reuse the stock market dataset from (sto, [n.d.]) also used in
related work (Poppe et al., 2021; Poppe et al., 2019, 2017a, 2017b) to
evaluate the effectiveness of CER processing strategies. This dataset contains
approximately 225k transaction records of 10 stocks from NYSE in a single day,
listing stock name, transaction ID, volume, price, time, and transaction type
(SELL/BUY). We use the transaction type to divide the dataset into two
streams: one stream of SELL events, and one steam of BUY events.

Queries. The workload of sequence queries with output over the stock market
dataset are the following queries of length $3$, $6$, $9$, $12$ and $24$,
respectively:

    ΨΨS3 = SELECT * FROM S
    ΨΨ     WHERE (SELL as T1; BUY as T2; BUY as T3)
    ΨΨ     FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’]
    ΨΨ     WITHIN 10000 [stock_time]
    Ψ
    ΨΨS6 = SELECT * FROM S
    ΨΨ     WHERE (SELL as T1; BUY as T2; BUY as T3;
    ΨΨ            SELL as T4; BUY as T5; BUY as T6)
    ΨΨ     FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    ΨΨ            T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’]
    ΨΨ     WITHIN 10000 [stock_time]
    ΨΨ
    ΨΨS9 = SELECT * FROM S
    ΨΨ     WHERE (SELL as T1; BUY as T2; BUY as T3;
    ΨΨ            SELL as T4; BUY as T5; BUY as T6;
    ΨΨ            SELL as T7; BUY as T8; BUY as T9)
    ΨΨ     FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    ΨΨ            T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’] AND
    ΨΨ            T7[name = ’YHOO’] AND T8[name = ’DELL’] AND T9[name = ’ORCL’]
    ΨΨ     WITHIN 10000 [stock_time]
    ΨΨ
    ΨΨS12 = SELECT * FROM S
    ΨΨ      WHERE (SELL as T1; BUY as T2; BUY as T3;
    ΨΨ             SELL as T4; BUY as T5; BUY as T6;
    ΨΨ             SELL as T7; BUY as T8; BUY as T9;
    ΨΨ             SELL as T10; BUY as T11; BUY as T12)
    ΨΨ      FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    ΨΨ             T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’] AND
    ΨΨ             T7[name = ’YHOO’] AND T8[name = ’DELL’] AND T9[name = ’ORCL’] AND
    ΨΨ             T10[name = ’MSFT’] AND T11[name = ’INTC’] AND T12[name = ’RIMM’]
    ΨΨ      WITHIN 10000 [stock_time]
    ΨΨ
    ΨΨS24 = SELECT * FROM S
    ΨΨ      WHERE (SELL as T1; BUY as T2; BUY as T3;
    ΨΨ             SELL as T4; BUY as T5; BUY as T6;
    ΨΨ             SELL as T7; BUY as T8; BUY as T9;
    ΨΨ             SELL as T10; BUY as T11; BUY as T12;
    ΨΨ             SELL as T13; BUY as T14; BUY as T15;
    ΨΨ             SELL as T16; BUY as T17; BUY as T18;
    ΨΨ             SELL as T19; BUY as T20; BUY as T21;
    ΨΨ             SELL as T22; BUY as T23; BUY as T24)
    ΨΨ      FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    ΨΨ             T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’] AND
    ΨΨ             T7[name = ’YHOO’] AND T8[name = ’DELL’] AND T9[name = ’ORCL’] AND
    ΨΨ             T10[name = ’MSFT’] AND T11[name = ’INTC’] AND T12[name = ’RIMM’] AND
    ΨΨ             T13[name = ’INTC’] AND T14[name = ’RIMM’] AND T15[name = ’QQQ’] AND
    ΨΨ             T16[name = ’IPIX’] AND T17[name = ’AMAT’] AND T18[name = ’CSCO’] AND
    ΨΨ             T19[name = ’YHOO’] AND T20[name = ’DELL’] AND T21[name = ’ORCL’] AND
    ΨΨ             T22[name = ’MSFT’] AND T23[name = ’INTC’] AND T24[name = ’RIMM’]
    ΨΨ      WITHIN 10000 [stock_time]
    Ψ

For the workload of sequence queries without output, we extend each query of
the previous workload with a “non-existing” event. Queries S3’, S6’, S9’,
S12’, and S24’ are the aforementioned extension of S3, S6, S9, S12, and S24,
respectively :

    ΨS3’ = SELECT * FROM S
    Ψ      WHERE (SELL as T1; BUY as T2; BUY as T3; BUY as NE)
    Ψ      FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND NE[name = ’NotExists’]
    Ψ      WITHIN 10000 [stock_time]
    Ψ
    ΨS6’ = SELECT * FROM S
    Ψ      WHERE (SELL as T1; BUY as T2; BUY as T3;
    Ψ             SELL as T4; BUY as T5; BUY as T6; BUY AS NE)
    Ψ      FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    Ψ             T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’] AND NE[name = ’NotExists’]
    Ψ      WITHIN 10000 [stock_time]
    Ψ
    ΨS9’ = SELECT * FROM S
    Ψ      WHERE (SELL as T1; BUY as T2; BUY as T3;
    Ψ             SELL as T4; BUY as T5; BUY as T6;
    Ψ             SELL as T7; BUY as T8; BUY as T9; BUY AS NE)
    Ψ      FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    Ψ             T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’] AND
    Ψ             T7[name = ’YHOO’] AND T8[name = ’DELL’] AND T9[name = ’ORCL’] AND NE[name = ’NotExists’]
    Ψ      WITHIN 10000 [stock_time]
    Ψ
    ΨS12’ = SELECT * FROM S
    Ψ       WHERE (SELL as T1; BUY as T2; BUY as T3;
    Ψ              SELL as T4; BUY as T5; BUY as T6;
    Ψ              SELL as T7; BUY as T8; BUY as T9;
    Ψ              SELL as T10; BUY as T11; BUY as T12; BUY AS NE)
    Ψ       FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    Ψ              T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’] AND
    Ψ              T7[name = ’YHOO’] AND T8[name = ’DELL’] AND T9[name = ’ORCL’] AND
    Ψ              T10[name = ’MSFT’] AND T11[name = ’INTC’] AND T12[name = ’RIMM’] AND NE[name = ’NotExists’]
    Ψ       WITHIN 10000 [stock_time]
    Ψ
    ΨS24’ = SELECT * FROM S
    Ψ       WHERE (SELL as T1; BUY as T2; BUY as T3;
    Ψ              SELL as T4; BUY as T5; BUY as T6;
    Ψ              SELL as T7; BUY as T8; BUY as T9;
    Ψ              SELL as T10; BUY as T11; BUY as T12;
    Ψ              SELL as T13; BUY as T14; BUY as T15;
    Ψ              SELL as T16; BUY as T17; BUY as T18;
    Ψ              SELL as T19; BUY as T20; BUY as T21;
    Ψ              SELL as T22; BUY as T23; BUY as T24; BUY AS NE)
    Ψ       FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND
    Ψ              T4[name = ’IPIX’] AND T5[name = ’AMAT’] AND T6[name = ’CSCO’] AND
    Ψ              T7[name = ’YHOO’] AND T8[name = ’DELL’] AND T9[name = ’ORCL’] AND
    Ψ              T10[name = ’MSFT’] AND T11[name = ’INTC’] AND T12[name = ’RIMM’] AND
    Ψ              T13[name = ’INTC’] AND T14[name = ’RIMM’] AND T15[name = ’QQQ’] AND
    Ψ              T16[name = ’IPIX’] AND T17[name = ’AMAT’] AND T18[name = ’CSCO’] AND
    Ψ              T19[name = ’YHOO’] AND T20[name = ’DELL’] AND T21[name = ’ORCL’] AND
    Ψ              T22[name = ’MSFT’] AND T23[name = ’INTC’] AND T24[name = ’RIMM’] AND NE[name = ’NotExists’]
    Ψ       WITHIN 10000 [stock_time]

For the workload of sequence queries of length 3 with increasing time windows
and without output, we use query S3’ and modify the size of the time window by
$20$, $30$, and $40$ seconds as follow:

    ΨS3’ = SELECT * FROM S
    Ψ      WHERE (SELL as T1; BUY as T2; BUY as T3; BUY as NE)
    Ψ      FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND NE[name = ’NotExists’]
    Ψ      WITHIN 10000 [stock_time]
    Ψ
    ΨS3’x2 = SELECT * FROM S
    Ψ        WHERE (SELL as T1; BUY as T2; BUY as T3; BUY as NE)
    Ψ        FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND NE[name = ’NotExists’]
    Ψ        WITHIN 20000 [stock_time]
    Ψ
    ΨS3’x3 = SELECT * FROM S
    Ψ        WHERE (SELL as T1; BUY as T2; BUY as T3; BUY as NE)
    Ψ        FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND NE[name = ’NotExists’]
    Ψ        WITHIN 30000 [stock_time]
    Ψ
    ΨS3’x4 = SELECT * FROM S
    Ψ        WHERE (SELL as T1; BUY as T2; BUY as T3; BUY as NE)
    Ψ        FILTER T1[name = ’INTC’] AND T2[name = ’RIMM’] AND T3[name = ’QQQ’] AND NE[name = ’NotExists’]
    Ψ        WITHIN 40000 [stock_time]

Finally, for the last workout of sequence queries with selection strategies,
we consider queries S3’, S3’x2, S3’x3, and S3’x4 and use the selection
strategy provided by each system.

##  Appendix E Smart homes dataset

Dataset. We reuse the smart homes dataset from the DEBS 2014 Grand Challenge
(sma, [n.d.]), which contains events originating from smart plugs deployed in
private households. Each smart plug acts as a proxy between the wall power
outlet and the device connected to it, and is equipped with sensors to measure
power load and power work at a resolution of one measurement per second. The
full dataset consists of over 4055 million measurements for 2125 plugs
distributed across 40 houses. We select the substream of events of a single
house, with house id 28. This substream contains data from 85 plugs
distributed over 17 households in the stream. We process the first million
events, focusing on load measurements only. Each event consists of an event
id, the timestamp, the measured load value, the plug id, and the household id.

Queries. All queries look for sequences of measurements in different household
that are above the dataset average load of 76 Watts, in a time window of $10$
seconds (note that the plug timestamp is in seconds). The workload of sequence
queries with output over the smart homes dataset are the following queries of
length $3$, $6$, $9$, $12$ and $24$, respectively.888We note that, because L
is bound to all events in the sequence, the filter L[value > 76] requires all
events in the sequence to have a load value above 76.

    ΨΨH3 = SELECT * FROM S
    ΨΨ     WHERE (LOAD as L1; LOAD as L2; LOAD as L3) as L
    ΨΨ     FILTER L[value > 76] AND
    ΨΨ            L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4]
    ΨΨ     WITHIN 10 [plug_timestamp]
    ΨΨ
    ΨΨH6 = SELECT * FROM S
    ΨΨ     WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    ΨΨ            LOAD as L4; LOAD as L5; LOAD as L6) as L
    ΨΨ     FILTER L[value > 76] AND
    ΨΨ            L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    ΨΨ            L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10]
    ΨΨ     WITHIN 10 [plug_timestamp]

    ΨΨH9 = SELECT * FROM S
    ΨΨ     WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    ΨΨ            LOAD as L4; LOAD as L5; LOAD as L6;
    ΨΨ            LOAD as L7; LOAD as L8; LOAD as L9) as L
    ΨΨ     FILTER L[value > 76] AND
    ΨΨ            L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    ΨΨ            L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10] AND
    ΨΨ            L7[household_id = 12] AND L8[household_id = 14] AND L9[household_id = 15]
    ΨΨ     WITHIN 10 [plug_timestamp]
    ΨΨ
    ΨΨH12 = SELECT * FROM S
    ΨΨ      WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    ΨΨ             LOAD as L4; LOAD as L5; LOAD as L6;
    ΨΨ             LOAD as L7; LOAD as L8; LOAD as L9;
    ΨΨ             LOAD as L10; LOAD as L11; LOAD as L12) as L
    ΨΨ      FILTER L[value > 76] AND
    ΨΨ             L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    ΨΨ             L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10] AND
    ΨΨ             L7[household_id = 12] AND L8[household_id = 14] AND L9[household_id = 15] AND
    ΨΨ             L10[household_id = 4] AND L11[household_id = 9] AND L12[household_id = 10]
    ΨΨ      WITHIN 10 [plug_timestamp]
    ΨΨ
    ΨΨH24 = SELECT * FROM S
    ΨΨ      WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    ΨΨ             LOAD as L4; LOAD as L5; LOAD as L6;
    ΨΨ             LOAD as L7; LOAD as L8; LOAD as L9;
    ΨΨ             LOAD as L10; LOAD as L11; LOAD as L12;
    ΨΨ             LOAD as L13; LOAD as L14; LOAD as L15;
    ΨΨ             LOAD as L16; LOAD as L17; LOAD as L18;
    ΨΨ             LOAD as L19; LOAD as L20; LOAD as L21;
    ΨΨ             LOAD as L22; LOAD as L23; LOAD as L24) as L
    ΨΨ      FILTER L[value > 76] AND
    ΨΨ             L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    ΨΨ             L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10] AND
    ΨΨ             L7[household_id = 12] AND L8[household_id = 14] AND L9[household_id = 15] AND
    ΨΨ             L10[household_id = 4] AND L11[household_id = 9] AND L12[household_id = 10] AND
    ΨΨ             L13[household_id = 0] AND L14[household_id = 2] AND L15[household_id = 4] AND
    ΨΨ             L16[household_id = 6] AND L17[household_id = 9] AND L18[household_id = 10] AND
    ΨΨ             L19[household_id = 12] AND L20[household_id = 14] AND L21[household_id = 15] AND
    ΨΨ             L22[household_id = 4] AND L23[household_id = 9] AND L24[household_id = 10]
    ΨΨ      WITHIN 10 [plug_timestamp]
    Ψ

Similarly, we extend each query of the previous workload with a “non-existing”
event. The queries H3’, H6’, H9’, H12’, and H24’ are the corresponding
extensions of H3, H6, H9, H12, and H24:

    ΨH3’ = SELECT * FROM S
    Ψ      WHERE (LOAD as L1; LOAD as L2; LOAD as L3; LOAD as NE) as L
    Ψ      FILTER L[value > 76] AND
    Ψ             L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ             NE[household_id = 1000]
    Ψ      WITHIN 10 [plug_timestamp]
    Ψ
    ΨH6’ = SELECT * FROM S
    Ψ      WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    Ψ             LOAD as L4; LOAD as L5; LOAD as L6; LOAD as NE) as L
    Ψ      FILTER L[value > 76] AND
    Ψ             L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ             L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10] AND
    Ψ             NE[household_id = 1000]
    Ψ      WITHIN 10 [plug_timestamp]
    Ψ
    ΨH9’ = SELECT * FROM S
    Ψ      WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    Ψ             LOAD as L4; LOAD as L5; LOAD as L6;
    Ψ             LOAD as L7; LOAD as L8; LOAD as L9; LOAD as NE) as L
    Ψ      FILTER L[value > 76] AND
    Ψ             L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ             L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10] AND
    Ψ             L7[household_id = 12] AND L8[household_id = 14] AND L9[household_id = 15] AND
    Ψ             NE[household_id = 1000]
    Ψ      WITHIN 10 [plug_timestamp]
    Ψ
    ΨH12’ = SELECT * FROM S
    Ψ       WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    Ψ              LOAD as L4; LOAD as L5; LOAD as L6;
    Ψ              LOAD as L7; LOAD as L8; LOAD as L9;
    Ψ              LOAD as L10; LOAD as L11; LOAD as L12; LOAD as NE) as L
    Ψ       FILTER L[value > 76] AND
    Ψ              L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ              L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10] AND
    Ψ              L7[household_id = 12] AND L8[household_id = 14] AND L9[household_id = 15] AND
    Ψ              L10[household_id = 4] AND L11[household_id = 9] AND L12[household_id = 10] AND
    Ψ              NE[household_id = 1000]
    Ψ       WITHIN 10 [plug_timestamp]
    Ψ
    ΨH24’ = SELECT * FROM S
    Ψ       WHERE (LOAD as L1; LOAD as L2; LOAD as L3;
    Ψ              LOAD as L4; LOAD as L5; LOAD as L6;
    Ψ              LOAD as L7; LOAD as L8; LOAD as L9;
    Ψ              LOAD as L10; LOAD as L11; LOAD as L12;
    Ψ              LOAD as L13; LOAD as L14; LOAD as L15;
    Ψ              LOAD as L16; LOAD as L17; LOAD as L18;
    Ψ              LOAD as L19; LOAD as L20; LOAD as L21;
    Ψ              LOAD as L22; LOAD as L23; LOAD as L24; LOAD as NE) as L
    Ψ       FILTER L[value > 76] AND
    Ψ              L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ              L4[household_id = 6] AND L5[household_id = 9] AND L6[household_id = 10] AND
    Ψ              L7[household_id = 12] AND L8[household_id = 14] AND L9[household_id = 15] AND
    Ψ              L10[household_id = 4] AND L11[household_id = 9] AND L12[household_id = 10] AND
    Ψ              L13[household_id = 0] AND L14[household_id = 2] AND L15[household_id = 4] AND
    Ψ              L16[household_id = 6] AND L17[household_id = 9] AND L18[household_id = 10] AND
    Ψ              L19[household_id = 12] AND L20[household_id = 14] AND L21[household_id = 15] AND
    Ψ              L22[household_id = 4] AND L23[household_id = 9] AND L24[household_id = 10] AND
    Ψ              NE[household_id = 1000]
    Ψ       WITHIN 10 [plug_timestamp]

For the workload of sequence queries of length 3 with increasing time windows
and without output, we use query H3’ and modify the size of the time window by
$20$, $30$, and $40$ seconds:

    ΨH3’ = SELECT * FROM S
    Ψ      WHERE (LOAD as L1; LOAD as L2; LOAD as L3; LOAD as NE) as L
    Ψ      FILTER L[value > 76] AND
    Ψ             L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ             NE[household_id = 1000]
    Ψ      WITHIN 10 [plug_timestamp]
    Ψ
    ΨH3’x2 = SELECT * FROM S
    Ψ        WHERE (LOAD as L1; LOAD as L2; LOAD as L3; LOAD as NE) as L
    Ψ        FILTER L[value > 76] AND
    Ψ               L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ               NE[household_id = 1000]
    Ψ        WITHIN 20 [plug_timestamp]
    Ψ
    ΨH3’x3 = SELECT * FROM S
    Ψ        WHERE (LOAD as L1; LOAD as L2; LOAD as L3; LOAD as NE) as L
    Ψ        FILTER L[value > 76] AND
    Ψ               L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ               NE[household_id = 1000]
    Ψ        WITHIN 30 [plug_timestamp]
    Ψ
    ΨH3’x4 = SELECT * FROM S
    Ψ        WHERE (LOAD as L1; LOAD as L2; LOAD as L3; LOAD as NE) as L
    Ψ        FILTER L[value > 76] AND
    Ψ               L1[household_id = 0] AND L2[household_id = 2] AND L3[household_id = 4] AND
    Ψ               NE[household_id = 1000]
    Ψ        WITHIN 40 [plug_timestamp]

For the workout of sequence queries with selection strategies, H3’, H3’x2,
H3’x3, and H3’x4 are executed with the selection strategy provided by each
system.

##  Appendix F Taxi trips dataset

Dataset. We reuse the taxi trips dataset from the DEBS 2015 Grand Challenge
(tax, [n.d.]), which contains events reporting on taxi trips in New York,
listing the trip’s pickup and drop-off location, timestamps, information on
the taxi, and information related to the payment. Data are reported at the end
of the trip, i.e., upon arrival in the order of the drop-off timestamps. The
full dataset consists of 173 million events, of which we process the first
million. The original dataset contains absolute (latitude, longitue)
coordinates of pickup and dropoff locations. We preprocess events and use
reverse geo-location to convert these coordinates into corresponding zone
(E.g., East Harlem, Midwood, …) using the official definition of New York City
zones available at https://www1.nyc.gov/site/tlc/about/tlc-trip-record-
data.page.

Queries. Queries look for sequences of events where the dropoff location of
one event equals the pickup location of the next event. We search for this
pattern in a time window of 2.7 hours (i.e., 10000 seconds). Concretely, the
workload of sequence queries with output over the NY taxi trips are the
following queries of length $3$, $6$, $9$, $12$ and $24$, respectively:

    ΨΨT3 = SELECT * FROM S
    ΨΨ     WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3)
    ΨΨ     FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    ΨΨ            loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    ΨΨ            loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’]
    ΨΨ     WITHIN 10000 [dropoff_datetime]
    ΨΨ
    ΨΨT6 = SELECT * FROM S
    ΨΨ     WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    ΨΨ            TRIP as loc4; TRIP as loc5; TRIP as loc6)
    ΨΨ     FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    ΨΨ            loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    ΨΨ            loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    ΨΨ            loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    ΨΨ            loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    ΨΨ            loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    ΨΨ                 dropoff_loc = ’East Concourse/Concourse Village’]
    ΨΨ     WITHIN 10000 [dropoff_datetime]
    ΨΨ
    ΨΨT9 = SELECT * FROM S
    ΨΨ     WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    ΨΨ            TRIP as loc4; TRIP as loc5; TRIP as loc6;
    ΨΨ            TRIP as loc7; TRIP as loc8; TRIP as loc9)
    ΨΨ     FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    ΨΨ            loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    ΨΨ            loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    ΨΨ            loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    ΨΨ            loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    ΨΨ            loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    ΨΨ                 dropoff_loc = ’East Concourse/Concourse Village’] AND
    ΨΨ            loc7[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
    ΨΨ            loc8[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
    ΨΨ            loc9[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’]
    ΨΨ     WITHIN 10000 [dropoff_datetime]
    ΨΨ
    ΨΨT12 = SELECT * FROM S
    ΨΨ      WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    ΨΨ             TRIP as loc4; TRIP as loc5; TRIP as loc6;
    ΨΨ             TRIP as loc7; TRIP as loc8; TRIP as loc9;
    ΨΨ             TRIP as loc10; TRIP as loc11; TRIP as loc12)
    ΨΨ      FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    ΨΨ             loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    ΨΨ             loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    ΨΨ             loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    ΨΨ             loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    ΨΨ             loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    ΨΨ                  dropoff_loc = ’East Concourse/Concourse Village’] AND
    ΨΨ             loc7[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
    ΨΨ             loc8[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
    ΨΨ             loc9[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’] AND
    ΨΨ             loc10[pickup_loc = ’Gravesend’ AND dropoff_loc = ’Midwood’] AND
    ΨΨ             loc11[pickup_loc = ’Midwood’ AND dropoff_loc = ’Midwood’] AND
    ΨΨ             loc12[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’]
    ΨΨ      WITHIN 10000 [dropoff_datetime]
    ΨΨ
    ΨT24 = SELECT * FROM S
    Ψ      WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    Ψ             TRIP as loc4; TRIP as loc5; TRIP as loc6;
    Ψ             TRIP as loc7; TRIP as loc8; TRIP as loc9;
    Ψ             TRIP as loc10; TRIP as loc11; TRIP as loc12;
    Ψ             TRIP as loc13; TRIP as loc14; TRIP as loc15;
    Ψ             TRIP as loc16; TRIP as loc17; TRIP as loc18;
    Ψ             TRIP as loc19; TRIP as loc20; TRIP as loc21;
    Ψ             TRIP as loc22; TRIP as loc23; TRIP as loc24)
    Ψ      FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ             loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ             loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    Ψ             loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    Ψ             loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    Ψ                  dropoff_loc = ’East Concourse/Concourse Village’] AND
    Ψ             loc7[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ             loc8[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ             loc9[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc10[pickup_loc = ’Gravesend’ AND dropoff_loc = ’Midwood’] AND
    Ψ             loc11[pickup_loc = ’Midwood’ AND dropoff_loc = ’Midwood’] AND
    Ψ             loc12[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc13[pickup_loc = ’Gravesend’ and dropoff_loc = ’Midwood’] AND
    Ψ             loc14[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc15[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ             loc16[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    Ψ             loc17[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    Ψ             loc18[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    Ψ                   dropoff_loc = ’East Concourse/Concourse Village’] AND
    Ψ             loc19[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ             loc20[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ             loc21[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc22[pickup_loc = ’Gravesend’ AND dropoff_loc = ’Midwood’] AND
    Ψ             loc23[pickup_loc = ’Midwood’ AND dropoff_loc = ’Midwood’] AND
    Ψ             loc24[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’]
    Ψ      WITHIN 10000 [dropoff_datetime]
    Ψ

The workload of sequence queries without output extends each query of the
previous workload with a “non-existing” event.

    ΨT3’ = SELECT * FROM S
    Ψ     WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3; TRIP as NE)
    Ψ     FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ            loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ            loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ            NE[pickup_loc = ’NotExists’]
    Ψ     WITHIN 10000 [dropoff_datetime]
    Ψ
    ΨT6’ = SELECT * FROM S
    Ψ      WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    Ψ            TRIP as loc4; TRIP as loc5; TRIP as loc6; TRIP as NE)
    Ψ      FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ             loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ             loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    Ψ             loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    Ψ             loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    Ψ                  dropoff_loc = ’East Concourse/Concourse Village’] AND
    Ψ             NE[pickup_loc = ’NotExists’]
    Ψ      WITHIN 10000 [dropoff_datetime]
    Ψ
    ΨT9’ = SELECT * FROM S
    Ψ      WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    Ψ             TRIP as loc4; TRIP as loc5; TRIP as loc6;
    Ψ             TRIP as loc7; TRIP as loc8; TRIP as loc9; TRIP as NE)
    Ψ      FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ             loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ             loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    Ψ             loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    Ψ             loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    Ψ                  dropoff_loc = ’East Concourse/Concourse Village’] AND
    Ψ             loc7[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ             loc8[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ             loc9[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             NE[pickup_loc = ’NotExists’]
    Ψ      WITHIN 10000 [dropoff_datetime]
    Ψ
    ΨT12’ = SELECT * FROM S
    Ψ       WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    Ψ              TRIP as loc4; TRIP as loc5; TRIP as loc6;
    Ψ              TRIP as loc7; TRIP as loc8; TRIP as loc9;
    Ψ              TRIP as loc10; TRIP as loc11; TRIP as loc12; TRIP as NE)
    Ψ       FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ              loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ              loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ              loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
    Ψ              loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
    Ψ              loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
    Ψ                   dropoff_loc = ’East Concourse/Concourse Village’] AND
    Ψ              loc7[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ              loc8[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
    Ψ              loc9[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’] AND
    Ψ              loc10[pickup_loc = ’Gravesend’ AND dropoff_loc = ’Midwood’] AND
    Ψ              loc11[pickup_loc = ’Midwood’ AND dropoff_loc = ’Midwood’] AND
    Ψ              loc12[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ              NE[pickup_loc = ’NotExists’]
    Ψ       WITHIN 10000 [dropoff_datetime]
    Ψ
    ΨT24’ = SELECT * FROM S
    Ψ       WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3;
    Ψ              TRIP as loc4; TRIP as loc5; TRIP as loc6;
    Ψ              TRIP as loc7; TRIP as loc8; TRIP as loc9;
    Ψ              TRIP as loc10; TRIP as loc11; TRIP as loc12;
    Ψ              TRIP as loc13; TRIP as loc14; TRIP as loc15;
    Ψ              TRIP as loc16; TRIP as loc17; TRIP as loc18;
    Ψ              TRIP as loc19; TRIP as loc20; TRIP as loc21;
    Ψ              TRIP as loc22; TRIP as loc23; TRIP as loc24; TRIP as NE)
               FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
                      loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
                      loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
                      loc4[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
                      loc5[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
                      loc6[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
                           dropoff_loc = ’East Concourse/Concourse Village’] AND
                      loc7[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
                      loc8[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
                      loc9[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’] AND
                      loc10[pickup_loc = ’Gravesend’ AND dropoff_loc = ’Midwood’] AND
                      loc11[pickup_loc = ’Midwood’ AND dropoff_loc = ’Midwood’] AND
                      loc12[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
                      loc13[pickup_loc = ’Gravesend’ and dropoff_loc = ’Midwood’] AND
                      loc14[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
                      loc15[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
                      loc16[pickup_loc = ’West Brighton’ AND dropoff_loc = ’Lincoln Square West’] AND
                      loc17[pickup_loc = ’Lincoln Square West’ AND dropoff_loc = ’Sutton Place/Turtle Bay North’] AND
                      loc18[pickup_loc = ’Sutton Place/Turtle Bay North’ AND
                            dropoff_loc = ’East Concourse/Concourse Village’] AND
                      loc19[pickup_loc = ’East Concourse/Concourse Village’ AND dropoff_loc = ’East Harlem North’] AND
                      loc20[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’East Harlem North’] AND
                      loc21[pickup_loc = ’East Harlem North’ AND dropoff_loc = ’Gravesend’] AND
                      loc22[pickup_loc = ’Gravesend’ AND dropoff_loc = ’Midwood’] AND
                      loc23[pickup_loc = ’Midwood’ AND dropoff_loc = ’Midwood’] AND
                      loc24[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
                      NE[pickup_loc = ’NotExists’]
    Ψ       WITHIN 10000 [dropoff_datetime]

For the workload of sequence queries of length 3 with increasing time windows
and without output, we use query T3’ and modify the size of the time window by
$20$, $30$, and $40$ seconds as follow:

    ΨT3’ = SELECT * FROM S
    Ψ      WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3; TRIP as NE)
    Ψ      FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ             loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ             loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ             NE[pickup_loc = ’NotExists’]
    Ψ      WITHIN 10000 [dropoff_datetime]
    Ψ
    ΨT3’x2 = SELECT * FROM S
    Ψ        WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3; TRIP as NE)
    Ψ        FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ               loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ               loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ               NE[pickup_loc = ’NotExists’]
    Ψ        WITHIN 20000 [dropoff_datetime]
    Ψ
    ΨT3’x3 = SELECT * FROM S
    Ψ        WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3; TRIP as NE)
    Ψ        FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ               loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ               loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ               NE[pickup_loc = ’NotExists’]
    Ψ        WITHIN 30000 [dropoff_datetime]
    Ψ
    ΨT3’x4 = SELECT * FROM S
    Ψ        WHERE (TRIP as loc1; TRIP as loc2; TRIP as loc3; TRIP as NE)
    Ψ        FILTER loc1[pickup_loc = ’East Harlem North’ and dropoff_loc = ’Midwood’] AND
    Ψ               loc2[pickup_loc = ’Midwood’ AND dropoff_loc = ’Gravesend’] AND
    Ψ               loc3[pickup_loc = ’Gravesend’ AND dropoff_loc = ’West Brighton’] AND
    Ψ               NE[pickup_loc = ’NotExists’]
    Ψ        WITHIN 40000 [dropoff_datetime]

The last workout of sequence queries with selection strategies uses T3’,
T3’x2, T3’x3, and T3’x4 with the selection strategy provided by each system.

##  Appendix G Stock market queries with other operators

The specification of the stock market queries $Q_{1}$ to $Q_{7}$ is the
following:

    ΨΨQ1 = SELECT * FROM S
    ΨΨ     WHERE (SELL as msft; BUY as oracle; BUY as csco; SELL as amat)
    ΨΨ     FILTER msft[name = ’MSFT’] AND oracle[name = ’ORCL’] AND
    ΨΨ            csco[name = ’CSCO’] AND amat[name = ’AMAT’]
    ΨΨ     WITHIN 30000 [stock_time]
    ΨΨ
    ΨΨQ2 = SELECT * FROM S
    ΨΨ     WHERE (SELL as msft; BUY as oracle; BUY as csco; SELL as amat)
    ΨΨ     FILTER msft[name = ’MSFT’] AND msft[price > 26.0] AND
    ΨΨ            oracle[name = ’ORCL’] AND oracle[price > 11.14] AND
    ΨΨ            csco[name = ’CSCO’] AND amat[name = ’AMAT’] AND amat[price >= 18.92]
    ΨΨ     WITHIN 30000 [stock_time]
    ΨΨ
    ΨΨQ3 = SELECT * FROM S
    ΨΨ     WHERE (SELL as msft; BUY as oracle; BUY as csco; SELL as amat)
    ΨΨ     FILTER msft[name = ’MSFT’] AND oracle[name = ’ORCL’] AND
    ΨΨ            csco[name = ’CSCO’] AND amat[name = ’AMAT’]
    ΨΨ     PARTITION BY [volume]
    ΨΨ     WITHIN 30000 [stock_time]
    ΨΨ     CONSUME BY ANY
    ΨΨ
    ΨΨQ4 = SELECT * FROM S
    ΨΨ     WHERE (SELL as msft; (BUY OR SELL) as oracle; (BUY OR SELL) as csco; SELL as amat)
    ΨΨ     FILTER msft[name = ’MSFT’] AND oracle[name = ’ORCL’] AND
    ΨΨ            csco[name = ’CSCO’] AND amat[name = ’AMAT’]
    ΨΨ     WITHIN 30000 [stock_time]
    ΨΨ
    ΨΨQ5 = SELECT * FROM S
    ΨΨ     WHERE (SELL as msft; (BUY OR SELL) as oracle; (BUY OR SELL) as csco; SELL as amat)
    ΨΨ     FILTER msft[name = ’MSFT’] AND msft[price > 26.0] AND
    ΨΨ            oracle[name = ’ORCL’] AND oracle[price > 11.14] AND
    ΨΨ            csco[name = ’CSCO’] AND amat[name = ’AMAT’] AND amat[price >= 18.92]
    ΨΨ     WITHIN 30000 [stock_time]
    ΨΨ
    ΨΨQ6 = SELECT * FROM S
    ΨΨ     WHERE (SELL as msft; (BUY OR SELL) as oracle; (BUY OR SELL) as csco; SELL as amat)
    ΨΨ     FILTER msft[name = ’MSFT’] AND oracle[name = ’ORCL’] AND
    ΨΨ            csco[name = ’CSCO’] AND amat[name = ’AMAT’]
    ΨΨ     PARTITION BY [volume]
    ΨΨ     WITHIN 30000 [stock_time]
    ΨΨ     CONSUME BY ANY
    ΨΨ
    ΨΨQ7 = SELECT * FROM S
    ΨΨ     WHERE (SELL as msft; (BUY OR SELL)+ as qqq; SELL as amat)
    ΨΨ     FILTER msft[name = ’MSFT’] AND qqq[name = ’QQQ’] and
    ΨΨ            qqq[volume=4000] AND amat[name = ’AMAT’]
    ΨΨ     WITHIN 30000 [stock_time]
    Ψ

Next, we briefly explain each query. $Q_{1}$ is a sequence query looking for a
sequence SELL;BUY;BUY;SELL of four major tech companies. $Q_{2}$ restricts
$Q_{1}$ by filtering the price of each stock over a certain threshold (similar
than in Example LABEL:ex:cer-hard). Instead, $Q_{3}$ is a restricted version
$Q_{1}$ with a partition-by clause over the stock volume. $Q_{4}$ is for
testing disjunction by allowing $Q_{1}$ to test for BUY OR SELL in the two
middle events. $Q_{5}$ and $Q_{6}$ are the analogs of $Q_{2}$ and $Q_{3}$,
extending now $Q_{4}$ with filters and partition-by, respectively. Indeed,
$Q_{5}$ contains the same features as Example LABEL:ex:cer-hard. Finally,
$Q_{7}$ combines disjunction and iteration, searching for a pattern of the
form SELL;(BUY OR SELL)+;SELL.

For all queries, we used a time windows of 30 seconds (e.g., 30,000
milliseconds) over the stock_time attribute. We measure the throughput of the
stock market stream, and it gives 4,803 e/s. Thus, using a time window of 30
seconds, we will have approximately 100 active events in the window, which is
comparable with the experiments that we performed over synthetic data.

##  Appendix H Experiments with selection strategies

Many CER systems offer so-called selection strategies (Giatrakos et al., 2020;
Cugola and Margara, 2012b; Wu et al., 2006; Zhang et al., 2014). A selection
strategy can be seen as a heuristic for evaluating a query, where the system
is asked to return only a specific subset of all matched complex event. Since
this subset is often easier to recognize, it improves performance.

In the next experiment, we compare all systems in the presence of selection
strategies. For this, we redo the experiments of fixing the sequence length to
3, adding a final non-existing event (i.e., no output), and varying the window
length from T to 4T, but this time we allow each system to use its own
selection strategy. Unfortunately, each system has its own algorithm for
selection strategy and, thus, it is not possible to guarantee that everyone
generates the same outputs. Given that there is no output in this experiment
setup, we can argue that all systems are hence performing a similar task;
namely, we test the case where the selection strategy found no result (i.e.,
an unusual event). Nevertheless, the systems are still free to adopt their
performance-improving heuristics, consistent with their selection strategy.

For each system we use the selection strategy that gives better performance
for this experiment (except for FlinkCEP that was already using a selection
strategy in all experiments). Instead, CORE implements four different
selection strategies: ALL (no selection strategy), NEXT, LAST, and MAX (see
(Grez et al., 2021) for the semantics of each selection strategy). All are
implemented at the automata level, doing a sophisticated determinization
procedure to filter outputs, namely, the algorithm is the same (see Section
4), but the underlying automaton is different. Then for CORE we use LAST
selection strategy, which it is the most heavy selection strategy compared
with NEXT, MAX, and ALL (i.e., regarding determinization of the automaton) and
it produces a single output per pattern occurrence, similar to all other
systems.

Figure 11. Throughput as a function of time-window size when using selection
strategies.

In Figure 11, we display the throughput, separated by dataset, of each system
running with a selection strategy. From here, we can conclude that the use of
a selection strategy improves the performance of Esper, SASE, and OpenCEP.
Esper still suffers with the time windows size, decreasing its performance
exponentially when the window size increases (e.g., Stock Market). SASE and
OpenCEP do not incur on this cost, having a stable throughput and, moreover,
increasing it up to $10^{3}$ and $10^{4}$, respectively. Despite this
improvement, CORE’s throughput is at least two OOM above other systems (i.e.,
$10^{6}$ e/s) and stable when the window size increases. Therefore, we can
conclude then that the advantage of CORE is in the evaluation algorithm rather
than in the use of selection strategies.