Maximizing synchronization for aligning observed and modelled behaviour

Vincent Bloemen, Sebastiaan J. van Zelst, Wil M.P. van der Aalst, Boudewijn F. van Dongen, Jaco van de Pol

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

Conformance checking is a branch of process mining that aims to assess to what degree event data originating from the execution of a (business) process and a corresponding reference model conform to each other. Alignments have been recently introduced as a solution for conformance checking and have since rapidly developed into becoming the de facto standard. The state-of-the-art method to compute alignments is based on solving a shortest path problem derived from the reference model and the event data. Within such a shortest path problem, a cost function is used to guide the search to an optimal solution. The standard cost-function treats mismatches in the model and log as equal. In this paper, we consider a variant of this standard cost function which maximizes the number of correct matches instead. We study the effects of using this cost-function compared to the standard cost function on both small and large models using over a thousand generated and industrial case studies. We further show that the alignment computation process can be sped up significantly in specific instances. Finally, we present a new algorithm for the computation of alignments on models with many log traces that is an order of magnitude faster (in maximizing synchronous moves) compared to the state-of-the-art A* based solution method, as a result of a preprocessing step on the model.

Original languageEnglish
Title of host publicationBusiness Process Management - 16th International Conference, BPM 2018, Proceedings
EditorsMarco Montali, Ingo Weber, Mathias Weske, Jan vom Brocke
Place of PublicationCham
PublisherSpringer
Pages233-249
Number of pages17
ISBN (Electronic)978-3-319-98648-7
ISBN (Print)978-3-319-98647-0
DOIs
Publication statusPublished - 1 Jan 2018
Event16th International Conference on Business Process Management, BPM 2018 - Sydney, Australia
Duration: 9 Sep 201814 Sep 2018

Publication series

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

Conference

Conference16th International Conference on Business Process Management, BPM 2018
CountryAustralia
CitySydney
Period9/09/1814/09/18

Fingerprint

Cost Function
Synchronization
Cost functions
Alignment
Shortest Path Problem
Reference Model
Process Mining
Business Process
Model
Preprocessing
Speedup
Branch
Optimal Solution
Maximise
Trace
Standards
Industry

Cite this

Bloemen, V., van Zelst, S. J., van der Aalst, W. M. P., van Dongen, B. F., & van de Pol, J. (2018). Maximizing synchronization for aligning observed and modelled behaviour. In M. Montali, I. Weber, M. Weske, & J. vom Brocke (Eds.), Business Process Management - 16th International Conference, BPM 2018, Proceedings (pp. 233-249). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11080 LNCS). Cham: Springer. https://doi.org/10.1007/978-3-319-98648-7_14
Bloemen, Vincent ; van Zelst, Sebastiaan J. ; van der Aalst, Wil M.P. ; van Dongen, Boudewijn F. ; van de Pol, Jaco. / Maximizing synchronization for aligning observed and modelled behaviour. Business Process Management - 16th International Conference, BPM 2018, Proceedings. editor / Marco Montali ; Ingo Weber ; Mathias Weske ; Jan vom Brocke. Cham : Springer, 2018. pp. 233-249 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{aab0ab32a4cb47e0ba6b8aed14e22856,
title = "Maximizing synchronization for aligning observed and modelled behaviour",
abstract = "Conformance checking is a branch of process mining that aims to assess to what degree event data originating from the execution of a (business) process and a corresponding reference model conform to each other. Alignments have been recently introduced as a solution for conformance checking and have since rapidly developed into becoming the de facto standard. The state-of-the-art method to compute alignments is based on solving a shortest path problem derived from the reference model and the event data. Within such a shortest path problem, a cost function is used to guide the search to an optimal solution. The standard cost-function treats mismatches in the model and log as equal. In this paper, we consider a variant of this standard cost function which maximizes the number of correct matches instead. We study the effects of using this cost-function compared to the standard cost function on both small and large models using over a thousand generated and industrial case studies. We further show that the alignment computation process can be sped up significantly in specific instances. Finally, we present a new algorithm for the computation of alignments on models with many log traces that is an order of magnitude faster (in maximizing synchronous moves) compared to the state-of-the-art A* based solution method, as a result of a preprocessing step on the model.",
author = "Vincent Bloemen and {van Zelst}, {Sebastiaan J.} and {van der Aalst}, {Wil M.P.} and {van Dongen}, {Boudewijn F.} and {van de Pol}, Jaco",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-98648-7_14",
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 = "233--249",
editor = "Marco Montali and Ingo Weber and Mathias Weske and {vom Brocke}, Jan",
booktitle = "Business Process Management - 16th International Conference, BPM 2018, Proceedings",
address = "Germany",

}

Bloemen, V, van Zelst, SJ, van der Aalst, WMP, van Dongen, BF & van de Pol, J 2018, Maximizing synchronization for aligning observed and modelled behaviour. 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. 233-249, 16th International Conference on Business Process Management, BPM 2018, Sydney, Australia, 9/09/18. https://doi.org/10.1007/978-3-319-98648-7_14

Maximizing synchronization for aligning observed and modelled behaviour. / Bloemen, Vincent; van Zelst, Sebastiaan J.; van der Aalst, Wil M.P.; van Dongen, Boudewijn F.; van de Pol, Jaco.

Business Process Management - 16th International Conference, BPM 2018, Proceedings. ed. / Marco Montali; Ingo Weber; Mathias Weske; Jan vom Brocke. Cham : Springer, 2018. p. 233-249 (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 proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Maximizing synchronization for aligning observed and modelled behaviour

AU - Bloemen, Vincent

AU - van Zelst, Sebastiaan J.

AU - van der Aalst, Wil M.P.

AU - van Dongen, Boudewijn F.

AU - van de Pol, Jaco

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Conformance checking is a branch of process mining that aims to assess to what degree event data originating from the execution of a (business) process and a corresponding reference model conform to each other. Alignments have been recently introduced as a solution for conformance checking and have since rapidly developed into becoming the de facto standard. The state-of-the-art method to compute alignments is based on solving a shortest path problem derived from the reference model and the event data. Within such a shortest path problem, a cost function is used to guide the search to an optimal solution. The standard cost-function treats mismatches in the model and log as equal. In this paper, we consider a variant of this standard cost function which maximizes the number of correct matches instead. We study the effects of using this cost-function compared to the standard cost function on both small and large models using over a thousand generated and industrial case studies. We further show that the alignment computation process can be sped up significantly in specific instances. Finally, we present a new algorithm for the computation of alignments on models with many log traces that is an order of magnitude faster (in maximizing synchronous moves) compared to the state-of-the-art A* based solution method, as a result of a preprocessing step on the model.

AB - Conformance checking is a branch of process mining that aims to assess to what degree event data originating from the execution of a (business) process and a corresponding reference model conform to each other. Alignments have been recently introduced as a solution for conformance checking and have since rapidly developed into becoming the de facto standard. The state-of-the-art method to compute alignments is based on solving a shortest path problem derived from the reference model and the event data. Within such a shortest path problem, a cost function is used to guide the search to an optimal solution. The standard cost-function treats mismatches in the model and log as equal. In this paper, we consider a variant of this standard cost function which maximizes the number of correct matches instead. We study the effects of using this cost-function compared to the standard cost function on both small and large models using over a thousand generated and industrial case studies. We further show that the alignment computation process can be sped up significantly in specific instances. Finally, we present a new algorithm for the computation of alignments on models with many log traces that is an order of magnitude faster (in maximizing synchronous moves) compared to the state-of-the-art A* based solution method, as a result of a preprocessing step on the model.

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

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

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

M3 - Conference contribution

AN - SCOPUS:85053628175

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 - 233

EP - 249

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

ER -

Bloemen V, van Zelst SJ, van der Aalst WMP, van Dongen BF, van de Pol J. Maximizing synchronization for aligning observed and modelled behaviour. In Montali M, Weber I, Weske M, vom Brocke J, editors, Business Process Management - 16th International Conference, BPM 2018, Proceedings. Cham: Springer. 2018. p. 233-249. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-98648-7_14