A Dynamic Programming Approach for Alignments on Process Trees

Lecture notes in business information processing, pp. 84–97

Abstract

Abstract A fundamental task in conformance checking is to compute optimal alignments between a given event log and a process model. In general, it is known that this unavoidably incurs high computational costs which, in turn, leads to poor scalability in practice. One angle to attack the complexity is to develop alignment algorithms that exploit particular syntactic restrictions of the underlying process models. In this article, we study alignments for process trees with unique labels. These models are the output of the Inductive Miner, a family of state-of-the-art process discovery algorithms also used by the leading process mining tools. Our main contribution is a novel algorithm that constructs optimal alignments for process trees with unique labels efficiently, i.e., in polynomial time. This is in contrast with general process trees where the problem is NP-complete and general workflow nets where the problem is PSPACE-hard. We give a proof-of-concept implementation of our algorithm in PM4Py and evaluate it on a collection of real-life event logs.

Authors 3

1. Christopher T. Schwanen corresponding Aachen Chair of Process and Data Science

   RWTH Aachen University

   Affiliation as printed

   Chair of Process and Data Science (PADS), RWTH Aachen University, Aachen, Germany

2. Wied Pakusa

   Federal University of Applied Administrative Sciences

   Affiliation as printed

   Federal University of Applied Administrative Sciences, Brühl, Germany

3. Wil M. P. van der Aalst Aachen Chair of Process and Data Science

   RWTH Aachen University

   Affiliation as printed

   Chair of Process and Data Science (PADS), RWTH Aachen University, Aachen, Germany