Online conformance checking: relating event streams to process models using prefix-alignments

The execution of business processes within a company generates traces of event data in its supporting information system. Typically we are able to extract such data from the company’s information system describing, for specific cases, e.g. an insurance claim, what activities have been performed over time. We often refer to a collection of such data as an event log. From a formal perspective, an event log is considered to be a multiset of sequences of executed process activities, or simply events. Consider Table 1, which depicts a simplified view of an event log. The event log describes the execution of activities related to a fictional compensation request process for concert tickets. For example, consider all events related to case 13 (represented by Case-id 13), i.e. a new request is registered by Luke, Harry subsequently examines the request, Petechecks the corresponding ticket, etc.

For each event recorded in the event log, we have information regarding its id, what activity it related to, which resource executed the activity and at what time it was executed. In general, we are able to obtain even more event data, for example what is the corresponding ticket id, what concert the ticket belongs to, what is the ticket price, etc. However, for the sake of simplicity we abstract from such data. In particular, in context of this paper, we are only interested in actual activities performed, instead of all possible data/resource aspects involved in the activity execution, i.e. we focus on the control-flow perspective. For example, based on Table 1 we deduce that for case 13, the sequence \(\langle \)register request, examine, check ticket, decide, pay compensation\(\rangle \) was performed. We assume the execution of activities to be atomic; hence, given the universe of activities \(\mathcal {A}\), an event log \(L\) is a multiset over sequences of \(\mathcal {A}\), i.e. \(L:\mathcal {A}^* \rightarrow \mathbb {N}_0\).

A process model describes the intended behaviour of a process. Although many process modelling formalisms exist, we focus on (labelled) Petri nets [14], which allow us to explicitly model concurrency in a concise and compact manner. In Fig. 2, we depict an example Petri net. The Petri net, like the example event log in Table 1, describes handling of a compensation request. It dictates that the first activity to be performed should always be register request. Subsequently, the examine and check ticket activities can be performed concurrently. However, we are also allowed to only perform the check ticket activity and subsequently make a decision, i.e. to skip the examination. After a decision is made, we are able to redo the examination and ticket check. However, such decision, i.e. to redo these activities, is not explicitly captured by the system. Eventually, either the pay compensation or the reject request activity is performed.

A Petri net consists of places and transitions. Places are used to represent the state of the described process, whereas transitions represent possible executable activities, subject to the state. The Petri net in Fig. 2 consists of 7 places (denoted \(P\)), i.e. \(P= \{p_i, p_1, \ldots , p_5, p_o\}\), visualized as circles. Formally, we represent the state of a Petri net in terms of a marking\(M\), which is a multiset of places, i.e. \(M:P\rightarrow \mathbb {N}_0\). For example, in Fig. 2 place \(p_i\) is marked with a token, visualized by a black dot. Thus, the marking of the Petri net in Fig. 2, as visualized, is \([p_i]\). The Petri net furthermore contains 8 transitions (denoted \(T\)), i.e. \(\{t_1, \ldots , t_8 \}\), visualized as boxes. Transitions allow us to manipulate a Petri net’s marking. A transition \(t\in T\) is enabled if all places \(p\) that have an outgoing arc to \(t\) contain a token. If a transition is enabled in marking \(M\), we write \(M[t\rangle \). An enabled transition is able to fire. If we fire a transition \(t\), it consumes a token from each place that has an outgoing arc to \(t\). Subsequently, a token is produced in each place that has an incoming arc from \(t\). For example, in Fig. 2, \(t_1\) is the only enabled transition in marking \([p_0]\), and, if it fires we obtain new marking \([p_1,p_2]\). In marking \([p_1,p_2]\), we are able to fire both \(t_2\) and \(t_3\), in any order. We are thus able to generate sequences of fired transitions, e.g. \(\langle t_1, t_2, t_3 \rangle \) and \(\langle t_1, t_3, t_2 \rangle \), which both yield marking \([p_3,p_4]\). Note that, in marking \([p_1,p_2]\), transition \(t_4\) is not (yet) enabled. If we fire \(t_3\), leading to marking \([p_1,p_4]\), transition \(t_4\) is enabled. When executing a sequence \(\sigma \in T^*\) of transitions from marking \(M\) results in \(M'\), we write \(M\xrightarrow {\sigma } M'\). We let \(\mathcal {M}\) denote the universe of all possible markings.

All transitions, except transition \(t_6\), have a single character label, e.g. transition \(t_1\) has label a. Typically, these labels represent actual activities that can be executed in the process described by the Petri net. For convenience, we also added more descriptive names, e.g. register request. Transition \(t_6\) is an invisible transition, i.e. it is able to manipulate the marking of the Petri net, without being noticed by the outside world. Also, there are two transitions with label d, i.e. \(t_4\) and \(t_5\).

We formally define a Petri net \(N\) as a tuple \(N= (P, T, F, \lambda )\), where \(P\) represents its places, \(T\) its transitions, \(F\subseteq (P\times T) \cup (T\times P)\) represents the flow relation, i.e. the arcs in Fig. 2. Observe that a place is only connected to a transition and vice versa, i.e. there is never an arc between two places/transitions. Finally, given a set of activity labels \(\varLambda \) and \(\tau \notin \varLambda \), \(\lambda :T\rightarrow \varLambda ^\tau \) represents the labelling function of \(N\). For example, \(\lambda (t_1) = a\) and \(\lambda (t_6) = \tau \).

We assume that a reference model of a process is designed by a human business process analyst/designer. We therefore assume that a process model has a certain level of quality, e.g. the Petri net is a sound workflow net [15, Definition 7]. We do not introduce the characteristics of such models, however, soundness guarantees that we are always able to reach a designated final marking \(M_f\), from any marking \(M\) reachable from designated initial marking \(M_i\). For the purpose of this paper, we assume that the Petri nets we consider also consist of this property, which we deem the proper termination assumption.

When we reconsider the example sequence of activities related to case 13, i.e. written short-hand as \(\langle a,b,c,d,e \rangle \), we observe that indeed by firing transitions \(t_1\), \(t_2\), \(t_3\), \(t_5\) and \(t_7\), such sequence of activities is produced by \(N_1\) in Fig. 2. If we consider another example trace, i.e. \(\langle x, a, d, e, z \rangle \), we observe some problems. For example, activities x and z are not labels of \(N_1\). Furthermore, according to \(N_1\), at least c must be executed in-between a and d.

Alignments allow us to identify and quantify the aforementioned problems and moreover allow us to express these deviations in terms of the reference model. Conceptually, an alignment is a mapping between the execution of transitions in the process model and the activities observed in a trace\(\sigma \) in a given event log \(L\). Consider Fig. 3, in which we present alignments for traces \(\langle a,b,c,d,e \rangle \) and \(\langle x, a, d, e, z \rangle \) w.r.t. Petri net \(N_1\). Alignments are sequences of pairs, e.g. \(\gamma _1 = \langle (a, t_1), (b,t_2), \ldots , (e, t_7) \rangle \). Each pair within an alignment is referred to as a move. The first element of a move refers to an activity of the trace, whereas the second element refers to a transition. The goal is to create pairs of the form \((a, t)\) s.t. \(\lambda (t) = a\), e.g. all moves in \(\gamma _1\) are of this form. The sequence of activity labels in the alignment needs to equal the input trace. The sequence of transitions in the alignment needs to correspond to a \(\sigma \in T^*\) s.t., given a designated initial marking \(M_i\) and final marking \(M_f\), we have \(M_i \xrightarrow {\sigma } M_f\). For \(N_1\), we have \(M_i = [p_i]\) and \(M_f = [p_o]\). In some cases, we are not able to construct a move of the form \((a, t)\) s.t. \(\lambda (t) = a\). In case of trace \(\langle x,a,d,e,z \rangle \), we are not able to map x and z to any transition in \(N_1\) with an equally valued label. Furthermore, we at least need to execute transition \(t_3\) in order to form a sequence of transitions that generates marking \(M_f\) from \(M_i\). In some cases we need to fire a transition \(t\) with \(\lambda (t) = \tau \), for which we again are not able to construct a label-transition mapping. In such cases, we use skip-symbol\(\gg \) in either the activity or the transition part of a move. For example, consider \(\gamma _2\) in Fig. 3, which contains three skip symbols. Verify that again, when ignoring skip symbols, the sequence of activity labels equals the input trace, and the sequence of transitions is valid for \(M_i\) and \(M_f\). If a move is of the form \((a, t)\), we call this a synchronous move, \((a, \gg )\) is an activity move and \((\gg , a)\) is a model move.

Given the definition of alignments as presented in Definition 1, several alignments, i.e. sequences of moves adhering to Definition 1, exist for a given trace and Petri net. For example, consider alignment \(\gamma _3\) depicted in Fig. 4 which, according to Definition 1, is an alignment of \(\langle x,a,d,e,z \rangle \) and \(N_1\) as well. The main difference between \(\gamma _2\) and \(\gamma _3\), i.e. both aligning trace \(\langle x,a,d,e,z \rangle \) with \(N_1\), is the fact that \(\gamma _2\) binds the execution of \(t_4\) to the observed activity d, whereas \(\gamma _3\) binds the execution of \(t_5\) to the observed activity d. Clearly, both explanations are possible, however, to be able to bind executed activity d to \(t_5\), and alignment \(\gamma _3\) requires the explicit execution of transition \(t_2\) as well. Since activity b is not observed in the given trace, we observe the presence of move \((\gg , t_2)\) in \(\gamma _3\), which is not needed in \(\gamma _2\). Both alignments are feasible; however, we prefer alignment \(\gamma _2\) over \(\gamma _3\) as it minimizes non-synchronous moves, i.e. moves of the form \((a, \gg )\) or \((\gg , t)\).

As exemplified by alignments \(\gamma _2\) and \(\gamma _3\), we need means to be able to rank and compare alignments and somehow express our preference of certain alignments w.r.t. others. To this end, we define a cost function over the moves of an alignment. The cost of an alignment is simply the sum of the costs of its individual moves. Typically synchronous moves are assigned a low, or even 0, cost. The costs of model and activity moves are usually higher than the costs of synchronous moves. Assume we assign cost 0 to synchronous moves and cost 1 to activity/model moves. In this case, the cost of \(\gamma _1\) is 0. The cost of alignment \(\gamma _2\) is 3, whereas the cost of alignment \(\gamma _3\) is 4. Hence, the cost of \(\gamma _2\) is lower than the cost of \(\gamma _3\), and we prefer it over \(\gamma _2\). Formally, we define the cost of a move as a function \(\delta :\mathcal {A}^{\gg } \times T^{\gg } \rightarrow \mathbb {R}_0\). The costs \(\kappa ^{\delta }\) of a sequence of moves \(\gamma \), given move cost function \(\delta \), are defined as \(\kappa ^{\delta }(\gamma ) = \sum ^{|\gamma |}_{i = 1} \delta (\gamma (i))\). In general, we are able to use an arbitrary instantiation of \(\delta \); however, in the remainder of the paper, we adopt the unit-cost function:Since we assume unit-costs throughout the paper, we omit \(\delta \) as superscript and simply refer to \(\kappa (\gamma )\). We write \(\gamma ^{opt}\) to refer to an optimal alignment, i.e. \(\gamma ^{opt} = \mathbf {arg\ min}_{\gamma \in \varGamma (N, \sigma , M_i, M_f)} \kappa (\gamma )\). Consequently, computing an optimal alignment is simply defined as a minimization problem. In [3], it is shown that computing an optimal alignment is equivalent to solving a shortest path problem on the state space of the synchronous product net of\(N\)and\(\sigma \). The exact nature of such synchronous product net and an equivalence proof of the two problems is outside the scope of this paper. Hence, we refer to [3] for these definitions and proofs. In this paper, we use the fact that an algorithm to find an optimal alignment exists and we use it as a black box. Finally, it is important to note that multiple optimal alignments exist.

Formally, an event stream is a, possibly infinite, sequence of events. An event is a pair consisting of a case-identifier and an activity. An event describes what activity is performed in context of what process instance (represented by the case-identifier). Event streams differ from event logs in two ways: (1) an event stream is potentially infinite and (2) behaviour seen for a case is incomplete, i.e. in future new events may be executed in context of a case.

A pair \((c,a) \in \mathcal {C}\times \mathcal {A}\) represents an event, i.e. activity \(a\) was executed in context of case \(c\). \(S(1)\) denotes the first event that we receive, whereas \(S{(i)}\) denotes the ith event. Consider stream \(S_1\) in Fig. 5 as an example where we show the emission of activities based on the process model in Fig. 2 using short-hand activity names. Observe that event (3, d) is emitted first (\(S_1(1) = (3,d)\)), event (4, a) is emitted second, etc. Our knowledge after receiving the third event, i.e. \(S_1(3) = (5,a)\), w.r.t. case 5, is different from our knowledge after receiving the fifth event. After the third event, for case 5, we observed \(\langle a \rangle \), whereas after the fifth event this is \(\langle a,b,c \rangle \).

We aim at computing alignments for the cases emitted onto an event stream, as they allow us to quantify deviations in a clear manner. Assume that we have only seen the first three events, i.e. (3, d), (4, a) and (5, a), of \(S_1\). The only activity seen for case 5 is activity a. An optimal alignment for case 5 is \(\langle (a,t_1), (\gg , t_3), (\gg , t_4), (\gg , t_7) \rangle \). After receiving the fourth event, i.e. (5, b), an optimal alignment for case 5 is \(\langle (a,t_1), (b, t_2), (\gg , t_3), (\gg , t_5), (\gg , t_7) \rangle \). In both cases, the costs of the alignments are 3. However, after receiving the first nine events on stream \(S_1\) we obtain activity sequence \(\langle a,b,c,d,e \rangle \) for case 5 with corresponding optimal alignment \(\langle (a,t_1), (b, t_2), (c, t_3), (d, t_5), (e, t_7) \rangle \) with costs 0. Thus, since the knowledge we possess about cases changes over time, computing conventional alignments prior to case completion is expected to lead to an overestimation of the true alignment costs. We do not assume explicit knowledge of case termination w.r.t. the events observed on the stream. Moreover, we aim at detecting potential behaviour during case execution as opposed to computing such figures after case completion. As indicated, doing so with conventional alignments is expected to lead to cost overestimation, and as a consequence, false positives from a deviation perspective. Therefore, we aim at computing prefix-alignments, which are specifically designed to incorporate trace incompleteness.

Prefix-alignments are a relaxed alternative to conventional alignments [3, Sect. 4.5]. In essence, they relax requirement two of Definition 1 in such way that after executing the \(T^{\gg }\)-part of the alignment, projected onto \(T\), the final marking \(M_f\)can still be reached. Formally, we rephrase requirement two to \(\exists _{\sigma ' \in T^*}\left( M_i \xrightarrow {(\pi _{2}(\gamma ))_{\downarrow _{T}} \cdot \sigma '} M_f\right) \). Consider Fig. 6 in which we depict two example prefix-alignments of incomplete trace \(\langle a,c,d \rangle \) and \(N_1\). Observe that, for both alignments we need to append either \(\langle t_7 \rangle \) or \(\langle t_8 \rangle \) to obtain marking \(M_f\), and thus, the relaxed requirement is satisfied. Similar to conventional alignments, several prefix-alignments exist that correctly align a prefix and a Petri net. Hence, we again need means to rank and compare prefix-alignments. For example, in Fig. 6 we prefer \(\overline{\gamma }_1\) over \(\overline{\gamma }_2\), since it only contains synchronous moves, whereas \(\overline{\gamma }_2\) contains a model move. Again, we define a cost function for prefix-alignments. Since a prefix-alignment, like a conventional alignment, is a sequences of moves, the cost of a prefix alignment is defined in the exact same manner to the costs of conventional alignments, i.e. it is simply the sum of the costs of its individual moves. Observe that cost function \(\kappa \) is defined over a sequence of moves, and thus, given some prefix-alignment \(\overline{\gamma }\), \(\kappa (\overline{\gamma })\) is readily defined.

As a consequence, we again have the notion of optimality. For example, \(\overline{\gamma }_1\) is an optimal prefix-alignment for \(\langle a,c,d \rangle \) and \(N_1\). We let \(\overline{\varGamma }\) denote the universe of possible prefix-alignments and let \(\overline{\varGamma }(N, \sigma , M_i, M_f)\) denote all possible prefix-alignments of \(\sigma \) and \(N\) given \(M_i\) and \(M_f\).

Interestingly, any optimal prefix-alignment of any prefix of a trace is always underestimating the costs of the optimal alignment of any of its possible suffixes, and thus, of the eventual completed trace.

The underestimating property is useful since, in an online setting, once an optimal prefix-alignment has nonzero costs, it guarantees that a deviation from the reference model is present. On the other hand, if a case is not properly terminated and will never terminate, yet the sequence of activities seen so far has a prefix-alignment cost of zero, we do not observe this type of deviation until we compute a corresponding conventional (optimal) alignment.

Any shortest path algorithm to compute conventional alignments, i.e. as briefly discussed in Sect.3.2, is easily altered to compute prefix-alignments. In fact, in line with the relaxation of requirement two of Definition 1, such alteration only consists of adding more states to the set of final states of the search problem. Hence, to compute optimal (prefix-)alignments we are able to use any algorithm designed for finding shortest paths in a graph. However, in [3] the \(A^*\) algorithm [16] is proposed and evaluated. In this paper, we simply assume that we are able to use an algorithm \(\overline{\alpha }\), i.e.:Here, we assume \(\overline{\alpha }(N, \sigma , M_i, M_f) \in \overline{\varGamma }(N, \sigma , M_i, M_f)\) and it is optimal. Observe that the proper termination assumption, w.r.t. the process models considered, guarantees that \(\overline{\alpha }\) always find an optimal prefix-alignment.

We aim at computing a prefix-alignment for each sequence of events seen so far for each case \(c\in \mathcal {C}\). In this paper, we primarily focus on the performance of prefix-alignment computation in an incremental setting; we therefore do not consider (the impact of) storing the information seen on the event stream in great detail. Henceforth, we assume the existence of a case administration \(D_{\mathcal {C}}:\mathcal {C}\times \mathbb {N}_0\rightarrow \overline{\varGamma }\), where, for \(i\ge 1\), \(D_{\mathcal {C}}(c, i)\) represents the currently known prefix-alignment related to case c after receiving events \(S(1), S(2), \ldots , S(i)\). Initially, we have \(D_{\mathcal {C}}(c,0) = \epsilon , \forall c\in \mathcal {C}\). For now, we assume that \(D_{\mathcal {C}}\) is able to store all most recent prefix-alignments for all cases. Such assumption, theoretically, requires infinite memory; hence in Sect. 5.3, we briefly discuss how to handle this problem, and the corresponding limitations in practice.

To compute prefix-alignments based on the event stream, we conceptually perform the following steps. When we receive an event related to a certain case, we check whether we previously computed a prefix-alignment for that case. In case we are guaranteed that the event refers to an activity move, i.e. because the activity simply has no corresponding label in the reference model, we append such activity move to the prefix-alignment. If this is not the case, we fetch the marking in the reference model, corresponding to the previous prefix-alignment. For example, given prefix alignment \(\langle (a,t_1) \rangle \) based on \(N_1\) (Fig. 2), the corresponding marking is \([p_1,p_2]\). If the event is the first event received for the case, we simply obtain marking \(M_i\). In case we are able to directly fire a transition within the obtained marking with the same label as the activity that the event refers to, we append a corresponding synchronous move to the previously computed prefix-alignment. Otherwise we use a shortest path algorithm, of which we present some parametrization in Sect. 5.2, to find a new (optimal) prefix-alignment. In Algorithm 1, we present an algorithmic description of the aforementioned rationale.

The algorithm expects a Petri net, initial- and final marking, an algorithm that computes optimal prefix-alignments and an event stream as an input. Note that, after receiving a new event, the case administration for index \(i-1\) is copied into the ith version, i.e. line 6. This operation is O(1) in practice. Since optimal prefix-alignments underestimate conventional alignment costs (Proposition 1), we are interested to what extent Algorithm 1 guarantees optimality of the prefix-alignments stored in \(D_{\mathcal {C}}\).

Theorem 1 proves that Algorithm 1 always computes optimal prefix-alignments for \((\pi _{\mathcal {A}^{\gg }}(\overline{\gamma }))_{\downarrow _{\mathcal {A}}}\), i.e. the sequence of activities currently stored within \(D_{\mathcal {C}}\) for some \(c\in \mathcal {C}\). Hence, combining this result with Proposition 1, we conclude that whenever the algorithm observes certain alignment costs exceeding 0, the corresponding conventional alignment has at least the same costs, or higher.

In the previous section, we used \(\overline{\alpha }\) completely as a black box and always solved a shortest path problem starting from \(M_i\). In this section, we show that we are able to exploit the previously calculated alignment for a case \(c\) in order to prune the search state-space. Moreover, we show means to limit the search by changing its starting point.

Thus far, we assumed \(D_{\mathcal {C}}\) to be of infinite memory, an infeasible assumption in practice. In an online setting, case administration \(D_{\mathcal {C}}\) needs to deploy some form of memory management that removes entries based on some case characteristic, e.g. age, relative frequency on the stream, etc. Examples of such mechanisms are reservoirs [17, 18], time decay-based data structures [19] and frequency approximation algorithms [20]. These techniques, at some point, remove prefix-alignments related to some, seemingly inactive, case. Note that this no longer guarantees that a prefix-alignment maintained in \(D_{\mathcal {C}}\) is always an underestimation for all activities emitted on the stream for case \(c\). In fact, Theorem 1 actually does not prove this, as it proves optimality for \((\pi _{1}(\overline{\gamma }))_{\downarrow _{\mathcal {A}}}\), which under assumption of infinite memory is equivalent to the previous statement. Moreover, if we receive activities related to a case that was previously deleted, we are falsely starting to compute new prefix-alignments for the case, i.e. there was some past behaviour that we no longer possess.

A way to solve this problem is by tracking what cases are removed from case administration. If new events appear related to such case, we simply ignore them. In such way, any element of the case administration truly relates to all behaviour emitted on the stream related to the case. However, again, at some point in time we need to drop cases from the secondary storage component. It is, however, reasonable to assume that the number of distinct cases is orders of magnitudes smaller than the number of events emitted onto the event stream.

We used a scientific workflow implemented in RapidProM which, conceptually, performs the following steps:

Observe that within the experiments we mimic event streams by visiting each event in a trace, one by one, e.g. if we have event log \(L= [\langle a,b,c \rangle , \langle a,c,b \rangle ]\), we generate event stream \(\langle (1,a), (1,b), (1,c), (2,a),(2,c),(2,b)\rangle \). Moreover, we align every trace-variant once, i.e. if \(\langle a,b,c \rangle \) occurs multiple times in the event log, we only align it once. In total, we have generated 18 different models, for which we generate 18 different event logs, each containing 1000 traces, yielding 18.000 noise-free traces. After applying the different types of noise, we obtain a total of 324.000 traces. Clearly, the number of events per trace greatly varies depending on the generated model; however, within our experiments, in total 44.537.728 events were processed (with varying algorithm parametrization). Out of these events, 12.151.510 state-space searches were performed.

Here, we present the results of the experiments, in line with the parametrization options as described in Sect. 5.2. We first present results related to using cost upper-bounds; later we present the results related to limited search.

In this section, we discuss the results of applying incremental alignment calculation based on real event data. We focus on the under/overestimation of true eventual conventional alignment cost, as well as the method’s performance. As a baseline, we compute conventional alignments every time we receive a new event. We use an event log originating from a Dutch hospital related to the treatment of patients suspected of having sepsis [24]. Since we do not have a reference model, we generated one based on a subset of the data. This generated process model still describes around \(90\%\) of the behaviour within the event log (computed using conventional alignments). The data set contains 15.214 events divided over 1.050 cases. Prefix-alignments were computed for 13.775 different events. We plot all results w.r.t. the aligned prefix length as noise percentages, i.e. used in Figs. 8 and 10, are unknown when using real event data. Finally note that the distribution of trace length within the data is heavily skewed and has a long infrequent tail. The majority of the trace’s length is below 30, hence, figures for prefix lengths above this value refer to a relatively limited set of cases. Nonetheless, we plot all results for all possible prefix lengths observed.

In Fig. 12, we present results related to computed alignment costs. We show results for using the incremental scheme proposed in this paper with window sizes 5, 10 and 20, and, the baseline (“Conventional”). In Fig. 12a, we show the average absolute alignment costs per prefix length. We observe that using a window size of 5 in general leads to higher alignment costs. This is explained by the fact that the relatively little window size does not allow us to revert any choices made in previous alignments, which consequently does not allow us to find an eventual global optimum. Interestingly, both window sizes 10 and 20 lead to, on average, comparable alignment costs to simply computing conventional alignments. However, in the beginning of cases, i.e. for small prefixes, as expected, computing conventional alignments leads to higher values. In Fig. 12b, we show the average cost difference w.r.t. the eventual alignment costs, i.e. after case completion. Interestingly, after initially overestimating eventual costs, conventional alignments underestimate the costs of conventional alignments quite severely. This can be explained by the fact that partial traces are aligned by a short path of model moves through the model combined with a limited set of activity moves.

In order to quantify the potential business impact of applying the (prefix-)alignment approach, we derive several different measures of relevance for the three different window sizes and the baseline. These figures are presented in Table 3. To obtain the results as presented, for each received event we define:

We acknowledge that alternative definitions of True/False Positives/Negatives are possible. Therefore, the results obtained are specific for the definition provided, as well as the data set of use. We observe that computing conventional alignments, for every event received, leads to better recall, i.e. \(\frac{{TP}}{{TP} + {FN}}\). This implies that the ratio of correctly observed deviations w.r.t. neglected deviations is better for the conventional approach. However, using the incremental scheme leads to significantly higher specificity (\(\frac{{TN}}{{TN}+{FP}}\)) and precision values (\(\frac{{TP}}{{TP} + {FP}}\)). Specifically for window sizes 10 and 20 we observe very high precision values. This in fact is in line with Proposition 1 and, moreover, shows that the results obtained with these window sizes are close to results for an infinite window size. Finally, we observe that the accuracy of window sizes 10 and 20 is comparable and higher than the alternative approaches, i.e. window size 5 and conventional. However, in terms of F1-score, simply calculating conventional alignments outperforms using the incremental scheme as proposed.

In Fig. 13, we show the performance of the different approaches in terms of enqueued states and visited states. Note that the results presented consider the full incremental scheme, i.e. if we are able to execute a synchronous move directly, queued/visited states equals 0. As expected, using a window size of 5 is most efficient. Window sizes 10 and 20 are less efficient yet for longer prefix lengths, they outperform computing conventional alignments. For window size 20, we do observe a peak in terms of computational complexity for prefix lengths of 10–20. Such peak is explained by the relatively inaccurate heuristic used within the \(A^*\)-searches performed for prefix-alignment computation. The drops in the chart relate to purely incremental alignment updates. We observe that computational complexity of conventional alignment computation is in general increasing when prefix length increases. The incremental-based approach seems not to suffer from this and shows relatively stabilizing behaviour.

Based on the experiments using real hospital data, we conclude that, for this specific data set, a window size of 10 is appropriate. As opposed to computing conventional alignments, it achieves precise results, i.e. whenever a deviation is detected it is reasonable to assume that this is indeed the case. Moreover, it outperforms computing conventional alignments in terms of computational complexity and memory usage.