  Process executions in organizations generate a large variety of data. Process
mining is a data-driven analytical approach for analyzing this data from a
business process point of view. Online conformance checking deals with finding
discrepancies between real-life and modeled process behavior on data streams.
The current state-of-the-art output of online conformance checking is a
prefix-alignment, which is used for pinpointing the exact deviations in terms
of the trace and the model while accommodating a trace's unknown termination in
a streaming setting. However, producing prefix-alignments entails a state space
search to find the shortest path from a common start state to a common end
state between the trace and the model. This is computationally expensive and
makes the method infeasible in an online setting. Previously, the trie data
structure has been shown to be efficient for constructing alignments, utilizing
a proxy log representing the process model in a finite way. This paper
introduces a new approximate algorithm (IWS) on top of the trie for online
conformance checking. The algorithm is shown to be fast, memory-efficient, and
able to output both a prefix and a complete alignment event-by-event while
keeping track of previously seen cases and their state. Comparative analysis
against the current state-of-the-art algorithm for finding prefix-alignments
shows that the IWS algorithm achieves, in some cases, an order of magnitude
faster execution time while having a smaller error cost. In extreme cases, the
IWS finds prefix-alignments roughly three orders of magnitude faster than the
current state of the art. The IWS algorithm includes a discounted decay time
setting for efficient memory usage and a look-ahead limit for improving
computation time. Finally, the algorithm is stress tested for performance using
a simulation of high-traffic event streams.
