Doctoral Meeting: 'Improving the performance of alignment-based conformance checking'

Process mining is responsible for discovering models from event logs, checking their validity against new event logs (conformance checking) and improving models when changes are detected. Conformance checking techniques compare a process model with an event log to analyze and quantify the deviations between real and modeled behavior. Alignment-based approaches are the most successful solutions for conformance checking, as alignments associate the observed behavior of the log with the modeled behavior, identifying the discrepancies which cause a minimal cost. However, the state of the art still struggles when facing complex models and logs: they explore more states than necessary and spend too much time exploring each state, leading to large runtimes. We present REACH, an algorithm based on the A* algorithm that computes optimal alignments efficiently. The core components of the proposal are a set of optimization techniques for reducing the number of states explored by the A* algorithm and a token-based replay for alignment computation. These improve performance by both reducing the number of states to explore and the required computation time per state respectively. We have tested our proposal with 227 pairs of logs and models, and we have compared it with 10 state-of-the-art approaches. Results show that REACH outperforms the other proposals in runtimes, and even aligns logs and models that no other algorithm is able to align.

Supervisor: Manuel Lama Penín