Efficient Approximate Conformance Checking Using Trie Data Structures

Awad, Ahmed; Raun, Kristo; Weidlich, Matthias

Efficient Approximate Conformance Checking Using Trie Data Structures

Date

2021

Authors

Awad, Ahmed

Raun, Kristo

Weidlich, Matthias

Publisher

IEEE

Abstract

Conformance 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.

Keywords

Estimation error,Runtime,Computational modeling,Data structures,Approximation algorithms,Encoding,Computational efficiency

Citation

Awad, A. et al. (2021) “Efficient Approximate Conformance Checking Using Trie Data Structures,” in 2021 3rd International Conference on Process Mining (ICPM), pp. 1–8.