Efficiently computing alignments: using the extended marking equation

Boudewijn F. van Dongen

doi:10.1007/978-3-319-98648-7_12

Efficiently computing alignments: using the extended marking equation

Boudewijn F. van Dongen

Process Analytics

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

23 Citations (Scopus)

9 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. When computing alignments for Petri nets, (Integer) Linear Programming problems based on the marking equation are typically used to guide the search. Solving such problems is the main driver for the time complexity of alignments. In this paper, we adopt existing work in such a way that (a) the extended marking equation is used rather than the marking equation and (b) the number of linear problems that is solved is kept at a minimum. To do so, we exploit fundamental properties of the Petri nets and we show that we are able to compute optimal alignments for models for which this was previously infeasible. Furthermore, using a large collection of benchmark models, we empirically show that we improve on the state-of-the-art in terms of time and memory complexity.

Original language	English
Title of host publication	Business Process Management - 16th International Conference, BPM 2018, Proceedings
Editors	Marco Montali, Ingo Weber, Mathias Weske, Jan vom Brocke
Place of Publication	Cham
Publisher	Springer
Pages	197-214
Number of pages	18
ISBN (Electronic)	978-3-319-98648-7
ISBN (Print)	978-3-319-98647-0
DOIs	https://doi.org/10.1007/978-3-319-98648-7_12
Publication status	Published - 1 Jan 2018
Event	16th International Conference on Business Process Management (BPM 2018) - Sydney, Australia Duration: 9 Sept 2018 → 14 Sept 2018 Conference number: 16 http://ceur-ws.org/Vol-2196/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11080 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

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-319-98648-7_12

Cite this

van Dongen, B. F. (2018). Efficiently computing alignments: using the extended marking equation. In M. Montali, I. Weber, M. Weske, & J. vom Brocke (Eds.), Business Process Management - 16th International Conference, BPM 2018, Proceedings (pp. 197-214). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11080 LNCS). Springer. https://doi.org/10.1007/978-3-319-98648-7_12

van Dongen, Boudewijn F. / Efficiently computing alignments : using the extended marking equation. Business Process Management - 16th International Conference, BPM 2018, Proceedings. editor / Marco Montali ; Ingo Weber ; Mathias Weske ; Jan vom Brocke. Cham : Springer, 2018. pp. 197-214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{465cbc51ee5d4edf8edcb49e62eba30c,

title = "Efficiently computing alignments: using the extended marking equation",

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. When computing alignments for Petri nets, (Integer) Linear Programming problems based on the marking equation are typically used to guide the search. Solving such problems is the main driver for the time complexity of alignments. In this paper, we adopt existing work in such a way that (a) the extended marking equation is used rather than the marking equation and (b) the number of linear problems that is solved is kept at a minimum. To do so, we exploit fundamental properties of the Petri nets and we show that we are able to compute optimal alignments for models for which this was previously infeasible. Furthermore, using a large collection of benchmark models, we empirically show that we improve on the state-of-the-art in terms of time and memory complexity.",

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

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

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-98648-7_12",

language = "English",

isbn = "978-3-319-98647-0",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "197--214",

editor = "Marco Montali and Ingo Weber and Mathias Weske and {vom Brocke}, Jan",

booktitle = "Business Process Management - 16th International Conference, BPM 2018, Proceedings",

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 2018, Efficiently computing alignments: using the extended marking equation. in M Montali, I Weber, M Weske & J vom Brocke (eds), Business Process Management - 16th International Conference, BPM 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11080 LNCS, Springer, Cham, pp. 197-214, 16th International Conference on Business Process Management (BPM 2018), Sydney, Australia, 9/09/18. https://doi.org/10.1007/978-3-319-98648-7_12

Efficiently computing alignments: using the extended marking equation. / van Dongen, Boudewijn F.
Business Process Management - 16th International Conference, BPM 2018, Proceedings. ed. / Marco Montali; Ingo Weber; Mathias Weske; Jan vom Brocke. Cham: Springer, 2018. p. 197-214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11080 LNCS).

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 - 2018/1/1

Y1 - 2018/1/1

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. When computing alignments for Petri nets, (Integer) Linear Programming problems based on the marking equation are typically used to guide the search. Solving such problems is the main driver for the time complexity of alignments. In this paper, we adopt existing work in such a way that (a) the extended marking equation is used rather than the marking equation and (b) the number of linear problems that is solved is kept at a minimum. To do so, we exploit fundamental properties of the Petri nets and we show that we are able to compute optimal alignments for models for which this was previously infeasible. Furthermore, using a large collection of benchmark models, we empirically show that we improve on the state-of-the-art in terms of time and memory complexity.

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. When computing alignments for Petri nets, (Integer) Linear Programming problems based on the marking equation are typically used to guide the search. Solving such problems is the main driver for the time complexity of alignments. In this paper, we adopt existing work in such a way that (a) the extended marking equation is used rather than the marking equation and (b) the number of linear problems that is solved is kept at a minimum. To do so, we exploit fundamental properties of the Petri nets and we show that we are able to compute optimal alignments for models for which this was previously infeasible. Furthermore, using a large collection of benchmark models, we empirically show that we improve on the state-of-the-art in terms of time and memory complexity.

KW - Alignments

KW - Conformance checking

KW - Process Mining

UR - http://www.scopus.com/inward/record.url?scp=85053600389&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98648-7_12

DO - 10.1007/978-3-319-98648-7_12

M3 - Conference contribution

AN - SCOPUS:85053600389

SN - 978-3-319-98647-0

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 197

EP - 214

BT - Business Process Management - 16th International Conference, BPM 2018, Proceedings

A2 - Montali, Marco

A2 - Weber, Ingo

A2 - Weske, Mathias

A2 - vom Brocke, Jan

PB - Springer

CY - Cham

Y2 - 9 September 2018 through 14 September 2018

ER -

van Dongen BF. Efficiently computing alignments: using the extended marking equation. In Montali M, Weber I, Weske M, vom Brocke J, editors, Business Process Management - 16th International Conference, BPM 2018, Proceedings. Cham: Springer. 2018. p. 197-214. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-98648-7_12

Efficiently computing alignments: using the extended marking equation

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this