Bloemen, Vincent, van Zelst, Sebastiaan J., van der Aalst, Wil M.P., van Dongen, Boudewijn F. & van de Pol, Jaco (2018). Maximizing synchronization for aligning observed and modelled behaviour. In Ingo Weber, Jan vom Brocke, Marco Montali & Mathias Weske (Eds.), Business Process Management – 16th International Conference, BPM 2018, Proceedings (pp. 233-249). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), No. 11080 LNCS). Springer.

Abstract

Conformance checking is a branch of process mining that aims to assess to what degree event data originating from the execution of a (business) process and a corresponding reference model conform to each other. Alignments have been recently introduced as a solution for conformance checking and have since rapidly developed into becoming the de facto standard. The state-of-the-art method to compute alignments is based on solving a shortest path problem derived from the reference model and the event data. Within such a shortest path problem, a cost function is used to guide the search to an optimal solution. The standard cost-function treats mismatches in the model and log as equal. In this paper, we consider a variant of this standard cost function which maximizes the number of correct matches instead. We study the effects of using this cost-function compared to the standard cost function on both small and large models using over a thousand generated and industrial case studies. We further show that the alignment computation process can be sped up significantly in specific instances. Finally, we present a new algorithm for the computation of alignments on models with many log traces that is an order of magnitude faster (in maximizing synchronous moves) compared to the state-of-the-art A* based solution method, as a result of a preprocessing step on the model.