Efficient Approximate Conformance Checking Using Trie Data Structures

Simple item page
dc.contributor.authorAwad, Ahmed
dc.contributor.authorRaun, Kristo
dc.contributor.authorWeidlich, Matthias
dc.date.accessioned2025-05-06T09:15:08Z
dc.date.available2025-05-06T09:15:08Z
dc.date.issued2021
dc.description.abstractConformance 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.
dc.identifier.citationAwad, A. et al. (2021) “Efficient Approximate Conformance Checking Using Trie Data Structures,” in 2021 3rd International Conference on Process Mining (ICPM), pp. 1–8.
dc.identifier.doihttps://doi.org/10.1109/ICPM53251.2021.9576845
dc.identifier.urihttps://bspace.buid.ac.ae/handle/1234/2930
dc.language.isoen
dc.publisherIEEE
dc.relation.ispartofseries2021 3rd International Conference on Process Mining (ICPM)1-8
dc.subjectEstimation error,Runtime,Computational modeling,Data structures,Approximation algorithms,Encoding,Computational efficiency
dc.titleEfficient Approximate Conformance Checking Using Trie Data Structures
dc.typeArticle
Files
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.35 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Dr Ahmed Awad