All Optimal k-Bounded Alignments Using the FM-Index

Alignments are a popular technique in process mining to compare pairs of process executions. Given a pair of process executions, an optimal alignment represents the commonalities with the minimum number of differences. Compared process executions are event sequences representing process model runs or traces in an event log. Alignments are used in different process mining operations, such as conformance checking and comparison of event logs, a.k.a. variants analysis or log delta analysis. Given an event sequence, several optimal alignments can exist, but the majority of alignment techniques focus on computing a single (optimal) solution. Often, it is due to the exponential complexity associated to the computation of all optimal alignments. To tackle this problem, we present a novel approach to compute all k-bounded optimal alignments, which uses a text indexing technique called FM-Index. Given a k, our approach computes optimal alignments with up to k differences. The approach is evaluated in the context of conformance checking and variants analysis using synthetic and real-life event logs. The results show the feasibility to compute all optimal alignments in a reasonable time. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

All Optimal k-Bounded Alignments Using the FM-Index Chapter in Scopus