Master Thesis - Efficient State-Space Traversal in Alignment Computation
Most organizations, in a variety of fields such as banking, insurance and healthcare, execute several different (business) processes. Modern information systems allow us to track, store and retrieve data related to the execution of such processes, in the form of event logs. Often, an organization has a global idea, or even a formal specification, of how the process is supposed to be executed. In other cases, laws and legislations dictate explicitly in what way a process is ought to be executed. Hence, it is in the company's interest to assess to what degree the execution of their processes is in line with the corresponding specification.
Conformance checking techniques, originating from the field of process mining, aim at solving the aforementioned problem. Conformance checking techniques allow us to quantify to what degree the actual execution of a process, as recorded in an event log, conforms to a corresponding process specification. Recently, alignments were introduced, which rapidly developed into the de-facto standard in conformance checking. The major advantage of alignments w.r.t. alternative conformance checking techniques, is the fact that deviations and/or mismatches are quantified in an exact, unambiguous manner.
When computing alignments, a given process model and the behaviour recorded in an event log are converted into a synchronous product net and a shortest path problem is subsequently solved on its state space. Typically, the well-known A*algorithm is used as an underlying solution to the shortest path problem. Moreover, several (in some cases alignment-specific) parametrization options are defined and applied on top of the basic A* algorithm solution.
The objective of this thesis is to investigate and develop novel efficiency techniques for alignment computation based on A* search algorithm applied to state space of the underlying synchronous product net. In particular, a recent incremental state space traversal approach will be thoroughly investigated as a starting point of this thesis. Theoretical foundations will be studied, and theorems/proofs will be clearly given, where required. In order to examine the efficiency improvement, novel approaches will be implemented in a process mining tool by using the programming languages Java and/or Python.
Knowledge of basic computer science concepts, good programming skills (Java/Python) and an interest in theoretical and practical aspects of process mining (i.e. conformance checking) recommended.
- Process Mining Book: Data Science in Action
- Coursera: Process Mining Course
- Paper: Replaying History on Process Models for Conformance Checking and Performance Analysis
- Paper: Tuning Alignment Computation: An Experimental Evaluation
- Paper: Efficiently Computing Alignments using the Extended Marking Equation (link-to-be-published)
Prof. Wil van der Aalst
ir. Sebastiaan van Zelst and Dr. Seran Uysal
For more Information