Efficient Approximate Conformance Checking Using Trie Data Structures
Loading...
Date
Journal Title
Journal ISSN
Volume Title
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.
Description
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.