Efficient Approximate Conformance Checking Using Trie Data Structures
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, approxim...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://bspace.buid.ac.ae/handle/1234/2930 https://ieeexplore.ieee.org/document/9576845 https://doi.org/10.1109/ICPM53251.2021.9576845 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|