Abstract
Conformance checking is considered to be anything where observed behaviour needs to be related to already modelled behaviour. Fundamental to conformance checking are alignments which provide a precise relation between a sequence of activities observed in an event log and a execution sequence of a model. However, computing alignments is a complex task, both in time and memory, especially when models contain large amounts of parallelism. In this tool paper we present the actual algorithm and memory structures used for the experiments of [15]. We discuss the time complexity of the algorithm, as well as the space and time complexity of the main data structures. We further present the integration in ProM and a basic code snippet in Java for computing alignments from within any tool.
| Original language | English |
|---|---|
| Title of host publication | Business Process Management Workshops - BPM 2018 International Workshops, Revised Papers |
| Editors | Florian Daniel, Quan Z. Sheng, Hamid Motahari |
| Publisher | Springer |
| Pages | 44-55 |
| Number of pages | 12 |
| ISBN (Print) | 9783030116408 |
| DOIs | |
| Publication status | Published - 29 Jan 2019 |
| Event | 16th International Conference on Business Process Management, BPM International Workshops 2018 - Sydney, Australia Duration: 9 Sep 2018 → 14 Sep 2018 |
Publication series
| Name | Lecture Notes in Business Information Processing |
|---|---|
| Volume | 342 |
| ISSN (Print) | 1865-1348 |
Conference
| Conference | 16th International Conference on Business Process Management, BPM International Workshops 2018 |
|---|---|
| Country | Australia |
| City | Sydney |
| Period | 9/09/18 → 14/09/18 |
Fingerprint
Keywords
- Alignments
- Conformance checking
- Process mining
Cite this
}
Efficiently computing alignments : algorithm and datastructures. / van Dongen, Boudewijn F.
Business Process Management Workshops - BPM 2018 International Workshops, Revised Papers. ed. / Florian Daniel; Quan Z. Sheng; Hamid Motahari. Springer, 2019. p. 44-55 (Lecture Notes in Business Information Processing; Vol. 342).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Efficiently computing alignments
T2 - algorithm and datastructures
AU - van Dongen, Boudewijn F.
PY - 2019/1/29
Y1 - 2019/1/29
N2 - Conformance checking is considered to be anything where observed behaviour needs to be related to already modelled behaviour. Fundamental to conformance checking are alignments which provide a precise relation between a sequence of activities observed in an event log and a execution sequence of a model. However, computing alignments is a complex task, both in time and memory, especially when models contain large amounts of parallelism. In this tool paper we present the actual algorithm and memory structures used for the experiments of [15]. We discuss the time complexity of the algorithm, as well as the space and time complexity of the main data structures. We further present the integration in ProM and a basic code snippet in Java for computing alignments from within any tool.
AB - Conformance checking is considered to be anything where observed behaviour needs to be related to already modelled behaviour. Fundamental to conformance checking are alignments which provide a precise relation between a sequence of activities observed in an event log and a execution sequence of a model. However, computing alignments is a complex task, both in time and memory, especially when models contain large amounts of parallelism. In this tool paper we present the actual algorithm and memory structures used for the experiments of [15]. We discuss the time complexity of the algorithm, as well as the space and time complexity of the main data structures. We further present the integration in ProM and a basic code snippet in Java for computing alignments from within any tool.
KW - Alignments
KW - Conformance checking
KW - Process mining
UR - http://www.scopus.com/inward/record.url?scp=85061389800&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-11641-5_4
DO - 10.1007/978-3-030-11641-5_4
M3 - Conference contribution
AN - SCOPUS:85061389800
SN - 9783030116408
T3 - Lecture Notes in Business Information Processing
SP - 44
EP - 55
BT - Business Process Management Workshops - BPM 2018 International Workshops, Revised Papers
A2 - Daniel, Florian
A2 - Sheng, Quan Z.
A2 - Motahari, Hamid
PB - Springer
ER -