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!
|
| _version_ | 1862980616178368512 |
|---|---|
| author | Awad, Ahmed |
| author2 | Raun, Kristo Weidlich, Matthias |
| author2_role | author author |
| author_facet | Awad, Ahmed Raun, Kristo Weidlich, Matthias |
| author_role | author |
| dc.creator.none.fl_str_mv | Awad, Ahmed Raun, Kristo Weidlich, Matthias |
| dc.date.none.fl_str_mv | 2021 2025-05-06T09:15:08Z 2025-05-06T09:15:08Z |
| dc.identifier.none.fl_str_mv | 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. https://bspace.buid.ac.ae/handle/1234/2930 https://ieeexplore.ieee.org/document/9576845 https://doi.org/10.1109/ICPM53251.2021.9576845 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | IEEE |
| dc.relation.none.fl_str_mv | 2021 3rd International Conference on Process Mining (ICPM)1-8 |
| dc.subject.none.fl_str_mv | Estimation error,Runtime,Computational modeling,Data structures,Approximation algorithms,Encoding,Computational efficiency |
| dc.title.none.fl_str_mv | Efficient Approximate Conformance Checking Using Trie Data Structures |
| dc.type.none.fl_str_mv | Article |
| description | 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. |
| id | budr_5692062991ef3282de1b9f772ecaf79f |
| identifier_str_mv | 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. |
| language_invalid_str_mv | en |
| network_acronym_str | budr |
| network_name_str | The British University in Dubai repository |
| oai_identifier_str | oai:bspace.buid.ac.ae:1234/2930 |
| publishDate | 2021 |
| publisher.none.fl_str_mv | IEEE |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Efficient Approximate Conformance Checking Using Trie Data StructuresAwad, AhmedRaun, KristoWeidlich, MatthiasEstimation error,Runtime,Computational modeling,Data structures,Approximation algorithms,Encoding,Computational efficiencyConformance 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.IEEE2025-05-06T09:15:08Z2025-05-06T09:15:08Z2021ArticleAwad, 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/2930https://ieeexplore.ieee.org/document/9576845https://doi.org/10.1109/ICPM53251.2021.9576845en2021 3rd International Conference on Process Mining (ICPM)1-8oai:bspace.buid.ac.ae:1234/29302025-08-13T07:45:19Z |
| spellingShingle | Efficient Approximate Conformance Checking Using Trie Data Structures Awad, Ahmed Estimation error,Runtime,Computational modeling,Data structures,Approximation algorithms,Encoding,Computational efficiency |
| title | Efficient Approximate Conformance Checking Using Trie Data Structures |
| title_full | Efficient Approximate Conformance Checking Using Trie Data Structures |
| title_fullStr | Efficient Approximate Conformance Checking Using Trie Data Structures |
| title_full_unstemmed | Efficient Approximate Conformance Checking Using Trie Data Structures |
| title_short | Efficient Approximate Conformance Checking Using Trie Data Structures |
| title_sort | Efficient Approximate Conformance Checking Using Trie Data Structures |
| topic | Estimation error,Runtime,Computational modeling,Data structures,Approximation algorithms,Encoding,Computational efficiency |
| url | https://bspace.buid.ac.ae/handle/1234/2930 https://ieeexplore.ieee.org/document/9576845 https://doi.org/10.1109/ICPM53251.2021.9576845 |