Master Thesis - Efficient State-Space Traversal in Alignment Computation

Contact

Sebastiaan J. van Zelst

Name

Sebastiaan J. van Zelst

Scientific Assistant - Fraunhofer FIT

Phone

work
+49 241 80 21911

Email

E-Mail

Contact

M. Seran Uysal

Name

M. Seran Uysal

Scientific Assistant

Phone

work
+49 241 80 21904

Email

E-Mail
 

Description

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.

Prerequisites

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.

Pointers

Supervisor

Prof. Wil van der Aalst

Advisors

ir. Sebastiaan van Zelst and Dr. Seran Uysal

For more Information

Send an e-mail to and/or . Make sure to include detailed information about your background and scores for completed courses.