  The execution of (business) processes generates valuable traces of event data
in the information systems employed within companies. Recently, approaches for
monitoring the correctness of the execution of running processes have been
developed in the area of process mining, i.e., online conformance checking. The
advantages of monitoring a process' conformity during its execution are clear,
i.e., deviations are detected as soon as they occur and countermeasures can
immediately be initiated to reduce the possible negative effects caused by
process deviations. Existing work in online conformance checking only allows
for obtaining approximations of non-conformity, e.g., overestimating the actual
severity of the deviation. In this paper, we present an exact, parameter-free,
online conformance checking algorithm that computes conformance checking
results on the fly. Our algorithm exploits the fact that the conformance
checking problem can be reduced to a shortest path problem, by incrementally
expanding the search space and reusing previously computed intermediate
results. Our experiments show that our algorithm outperforms comparable
state-of-the-art approximation algorithms.
