Awad, AhmedRaun, KristoWeidlich, Matthias2025-05-062025-05-062021Awad, A. et al. (2021) “Efficient Approximate Conformance Checking Using Trie Data Structures,” in 2021 3rd International Conference on Process Mining (ICPM), pp. 1–8.https://bspace.buid.ac.ae/handle/1234/2930Conformance checking compares a process model and recorded executions of a process, i.e., a log of traces. To this end, state-of-the-art approaches compute an alignment between a trace and an execution sequence of the model. Since the construction of alignments is computationally expensive, approximation schemes have been developed to strike a balance between the efficiency and the accuracy of conformance checking. Specifically, conformance checking may rely only on so-called proxy behavior, a subset of the behavior of the model. However, the question how such proxy behavior shall be represented for efficient alignment computation has been largely neglected. In this paper, we contribute a new formulation of the proxy behavior derived from a model for approximate conformance checking. By encoding the proxy behavior using a trie data structure, we obtain a logarithmically reduced search space for alignment computation compared to a set-based representation. We show how our algorithm supports the definition of a budget for alignment computation and also augment it with strategies for meta-heuristic optimization and pruning of the search space. Evaluation experiments with five real-world event logs show that our approach reduces the runtime of alignment construction by two orders of magnitude with a modest estimation error.enEstimation error,Runtime,Computational modeling,Data structures,Approximation algorithms,Encoding,Computational efficiencyArticlehttps://doi.org/10.1109/ICPM53251.2021.9576845