Efficiently computing alignments: algorithm and datastructures

Boudewijn F. van Dongen

doi:10.1007/978-3-030-11641-5_4

Efficiently computing alignments: algorithm and datastructures

Boudewijn F. van Dongen

Process Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

6 Downloads (Pure)

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	https://doi.org/10.1007/978-3-030-11641-5_4
Publication status	Published - 29 Jan 2019
Event	16th International Conference on Business Process Management (BPM 2018) - Sydney, Australia Duration: 9 Sep 2018 → 14 Sep 2018 Conference number: 16 http://ceur-ws.org/Vol-2196/

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 2018)
Abbreviated title	BPM 2018
Country/Territory	Australia
City	Sydney
Period	9/09/18 → 14/09/18
Other	Dissertation Award, Demonstration, and Industrial Track at BPM
Internet address	http://ceur-ws.org/Vol-2196/

Keywords

Alignments
Conformance checking
Process mining

Access to Document

10.1007/978-3-030-11641-5_4

Cite this

@inproceedings{7291f3c7fb39471ba3c52f4a67202dd1,

title = "Efficiently computing alignments: algorithm and datastructures",

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.",

keywords = "Alignments, Conformance checking, Process mining",

author = "{van Dongen}, {Boudewijn F.}",

year = "2019",

month = jan,

day = "29",

doi = "10.1007/978-3-030-11641-5_4",

language = "English",

isbn = "9783030116408",

series = "Lecture Notes in Business Information Processing",

publisher = "Springer",

pages = "44--55",

editor = "Florian Daniel and Sheng, {Quan Z.} and Hamid Motahari",

booktitle = "Business Process Management Workshops - BPM 2018 International Workshops, Revised Papers",

address = "Germany",

note = "16th International Conference on Business Process Management (BPM 2018), BPM 2018 ; Conference date: 09-09-2018 Through 14-09-2018",

url = "http://ceur-ws.org/Vol-2196/",

}

van Dongen, BF 2019, Efficiently computing alignments: algorithm and datastructures. in F Daniel, QZ Sheng & H Motahari (eds), Business Process Management Workshops - BPM 2018 International Workshops, Revised Papers. Lecture Notes in Business Information Processing, vol. 342, Springer, pp. 44-55, 16th International Conference on Business Process Management (BPM 2018), Sydney, Australia, 9/09/18. https://doi.org/10.1007/978-3-030-11641-5_4

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 - 16th International Conference on Business Process Management (BPM 2018)

AU - van Dongen, Boudewijn F.

N1 - Conference code: 16

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

Y2 - 9 September 2018 through 14 September 2018

ER -

Efficiently computing alignments: algorithm and datastructures

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this