Efficient Computation of Order-Aware Alignments

 

Student: David Wenderdel

Title: Efficient Computation of Order-Aware Alignments

Supervisor: Dr. Sebastiaan van Zelst

1st Examiner: Prof. Dr. Wil van der Aalst

2nd Examiner: Prof. Dr. Sander Leemans

Summary:

The use of various information systems supporting businesses in a variety of domains generates tons of data every second making it impossible to manually handle such data. Process mining covers the automated analysis of processes by providing general-purpose algorithms to gain insights into the underlying business process, based on the recorded event data. Conformance checking is one of the major subfields of process mining and covers the compliance between a process model and the recorded event data. Alignments are the state-of-the-art technique to compute compliance and provide diagnostics. However, most of the existing alignment algorithms ignore the partial and concurrent nature of processes. Moreover, alignments analyze the conformance only in terms of the compliance between the events of the event data and the activities of the process model, but not the compliance between their respective ordering relations. In this thesis, we formally define order-aware alignments and propose a novel approach to compute such alignments. While conventional alignments are computed with a single cost function that only penalizes certain activity occurrences, we introduce a secondary cost function that also quantifies the ordering relations between such activity occurrences. This approach, by definition, supports partially ordered event data. To compute order-aware alignments efficiently, we investigate several computational strategies including bidirectional search, and examine their applicability to our approach. We evaluate the proposed approach and its specific computational strategies with some real-world event logs. We also compare the efficiency of the computational strategies with existing strategies for conventional alignments, whereas our approach provides more insights. The evaluation shows that the computational strategy has a significant impact on the efficiency of the computation of order-aware alignments.