RT Journal Article
T1 REACH: Researching Efficient Alignment-based Conformance Checking
A1 Casas-Ramos, Jacobo
A1 Mucientes Molina, Manuel
A1 Lama Penín, Manuel
K1 Process mining
K1 Conformance checking
K1 Alignments
AB Conformance checking techniques compare how a process is supposed to be executed according to a model with how it is executed in reality according to an event log. Alignment-based approaches are the most successful solutions for conformance checking. Optimal alignments are a way of finding the best match between the real and the modeled behavior and identifying the differences. However, finding these optimal alignments is a challenging task, especially for complex cases where the log and the model have many events and paths. The difficulty lies in the computational complexity required to find these alignments. To address this problem, we propose an efficient algorithm named REACH based on the A* search algorithm. The core components of the proposal are the use of a partial reachability graph for faster execution of process models for alignment computation and a set of optimization techniques for reducing the number of states explored by the A* algorithm. These improve performance by both reducing the required computation time per state and the number of states to process respectively. To evaluate the performance and scalability, we conducted tests using 227 pairs of logs and models, comparing the results obtained with those from 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.
PB Elsevier
SN 0957-4174
YR 2024
FD 2024
LK http://hdl.handle.net/10347/32931
UL http://hdl.handle.net/10347/32931
LA eng
NO Expert Systems with Applications Volume 241, 2024, 122467
NO This research was partially funded by the Spanish Ministerio de Ciencia e Innovación (grant number PID2020-112623GB-I00), and the Galician Consellería de Cultura, Educación e Universidade (grant numbers ED431C 2018/29 and ED431G2019/04). These grants are co-funded by the European Regional Development Fund (ERDF). Jacobo Casas-Ramos is supported by the Spanish Ministerio de Universidades under the FPU national plan (grant number FPU19/06668).
DS Minerva
RD 28 abr 2026