Efficient State-Space Traversal in Alignment Computation

 

Student: Tian Li

Title: Efficient State-Space Traversal in Alignment Computation

Supervisor: Dr. Sebastiaan J. van Zelst

1st Examiner: Prof. Wil M.P. van der Aalst

2nd Examiner: Prof. Stefan Decker

Summary

With the advanced support of information systems, processes become increasingly digitized in companies. As event data describing the digital footprint of these processes is available in the underlying databases, these data can be analyzed to reveal what really happened during the execution of the process. However, real-world processes often deviate from the desired specification and can lead to misleading judgment, thus conformance checking evaluates whether event logs and process models conform to each other, and provides insight into the process. Alignments have proven to be a very useful technique for calculating conformance metrics, particularly, diagnostics. In this thesis, we explore several variations of alignment computation techniques, which either approximate or compute optimal alignments. Compared to traditional techniques, our proposed approaches aim at improving search efficiency mainly by reducing the number of states and arcs traversed during the search. This is achieved by introducing a caching set for the search, and propagating sequence information for every state expanded during the search. We evaluated the techniques with publicly available data sets and compared the results with existing approaches. The results show that the proposed algorithm computes the (optimal) alignment faster by preventing redundant exploration of the state space.