Computing Partial Order Alignments Using Net Unfoldings

Abstract

Conformance checking is a prominent subfield of process mining. It aims to quantify to what extent the observed data matches the intended process. The de-facto method to achieve this is called alignments, which is computed on a trace-by-trace basis. Computing them requires exploring the state-space of the combination of the process model Petri Net and the trace, called the synchronous product. This can result in a state-space explosion problem when the process model exhibits significant concurrency. Furthermore, by nature alignments are sequential, neglecting the concurrent behaviour present in many process models. Lastly, incremental computation of alignments has proven a complex problem, limiting its applicability in online settings. This thesis aims to tackle these limitations by proposing a new method of computing partial-order alignments based on directed Petri Net unfoldings. We evaluate this novel approach through a series of five experiments, focusing on assessing the performance characteristics of the algorithm. We investigated the impact of model structure, placement of deviations, incremental computation, and the overall time complexity. We further compared our approach with two implementations of traditional alignment computation. We found that our approach addresses the state-space explosion problem effectively, on average queuing fewer states than the two implementations compared. Despite this improvement in the state-space exploration, the average elapsed time for our approach is significantly higher than the two implementations compared against. We found this to be caused by the compound nature of the algorithm, resulting in increased performance degradation when backtracking occurs during the directed search. Incremental computation is possible with only minor adjustments to the proposed approach but comes at a further performance penalty. We conclude by stating that the proposed approach has some intrinsic advantages over traditional alignment computation, but suffers from extreme performance degradation under certain conditions, limiting the practical applicability.