Computing alignments of event data and process models

Sebastiaan J. van Zelst, Alfredo Bolt, Boudewijn F. van Dongen

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

The aim of conformance checking is to assess whether a process model and event data, recorded in an event log, conform to each other. In recent years, alignments have proven extremely useful for calculating conformance statistics. Computing optimal alignments is equivalent to solving a shortest path problem on the state space of the synchronous product net of a process model and event data. State-of-the-art alignment based conformance checking implementations exploit the -algorithm, a heuristic search method for shortest path problems, and include a wide range of parameters that likely influence their performance. In previous work, we presented a preliminary and exploratory analysis of the effect of these parameters. This paper extends the aforementioned work by means of large-scale statistically-sound experiments that describe the effects and trends of these parameters for different populations of process models. Our results show that, indeed, there exist parameter configurations that have a significant positive impact on alignment computation efficiency.

Original languageEnglish
Title of host publicationTransactions on Petri Nets and Other Models of Concurrency XIII
EditorsMaciej Koutny, Lars Michael Kristensen, Wojciech Penczek
Place of PublicationBerlin
PublisherSpringer
Pages1-26
Number of pages26
ISBN (Print)978-3-662-58380-7, 978-3-662-58381-4
DOIs
Publication statusPublished - 1 Jan 2018

Publication series

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

Fingerprint

Data Model
Process Model
Alignment
Computing
Shortest Path Problem
Exploratory Analysis
Heuristic Search
Heuristic Method
Search Methods
State Space
Likely
Statistics
Acoustic waves
Configuration
Range of data
Experiment
Experiments

Keywords

  • Alignments
  • Conformance checking
  • Process mining

Cite this

van Zelst, S. J., Bolt, A., & van Dongen, B. F. (2018). Computing alignments of event data and process models. In M. Koutny, L. M. Kristensen, & W. Penczek (Eds.), Transactions on Petri Nets and Other Models of Concurrency XIII (pp. 1-26). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11090 LNCS). Berlin: Springer. https://doi.org/10.1007/978-3-662-58381-4_1
van Zelst, Sebastiaan J. ; Bolt, Alfredo ; van Dongen, Boudewijn F. / Computing alignments of event data and process models. Transactions on Petri Nets and Other Models of Concurrency XIII. editor / Maciej Koutny ; Lars Michael Kristensen ; Wojciech Penczek. Berlin : Springer, 2018. pp. 1-26 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inbook{d5486afbc11b487d8bdf8e652e4fdce3,
title = "Computing alignments of event data and process models",
abstract = "The aim of conformance checking is to assess whether a process model and event data, recorded in an event log, conform to each other. In recent years, alignments have proven extremely useful for calculating conformance statistics. Computing optimal alignments is equivalent to solving a shortest path problem on the state space of the synchronous product net of a process model and event data. State-of-the-art alignment based conformance checking implementations exploit the -algorithm, a heuristic search method for shortest path problems, and include a wide range of parameters that likely influence their performance. In previous work, we presented a preliminary and exploratory analysis of the effect of these parameters. This paper extends the aforementioned work by means of large-scale statistically-sound experiments that describe the effects and trends of these parameters for different populations of process models. Our results show that, indeed, there exist parameter configurations that have a significant positive impact on alignment computation efficiency.",
keywords = "Alignments, Conformance checking, Process mining",
author = "{van Zelst}, {Sebastiaan J.} and Alfredo Bolt and {van Dongen}, {Boudewijn F.}",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-662-58381-4_1",
language = "English",
isbn = "978-3-662-58380-7",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "1--26",
editor = "Maciej Koutny and Kristensen, {Lars Michael} and Wojciech Penczek",
booktitle = "Transactions on Petri Nets and Other Models of Concurrency XIII",
address = "Germany",

}

van Zelst, SJ, Bolt, A & van Dongen, BF 2018, Computing alignments of event data and process models. in M Koutny, LM Kristensen & W Penczek (eds), Transactions on Petri Nets and Other Models of Concurrency XIII. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11090 LNCS, Springer, Berlin, pp. 1-26. https://doi.org/10.1007/978-3-662-58381-4_1

Computing alignments of event data and process models. / van Zelst, Sebastiaan J.; Bolt, Alfredo; van Dongen, Boudewijn F.

Transactions on Petri Nets and Other Models of Concurrency XIII. ed. / Maciej Koutny; Lars Michael Kristensen; Wojciech Penczek. Berlin : Springer, 2018. p. 1-26 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11090 LNCS).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - Computing alignments of event data and process models

AU - van Zelst, Sebastiaan J.

AU - Bolt, Alfredo

AU - van Dongen, Boudewijn F.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The aim of conformance checking is to assess whether a process model and event data, recorded in an event log, conform to each other. In recent years, alignments have proven extremely useful for calculating conformance statistics. Computing optimal alignments is equivalent to solving a shortest path problem on the state space of the synchronous product net of a process model and event data. State-of-the-art alignment based conformance checking implementations exploit the -algorithm, a heuristic search method for shortest path problems, and include a wide range of parameters that likely influence their performance. In previous work, we presented a preliminary and exploratory analysis of the effect of these parameters. This paper extends the aforementioned work by means of large-scale statistically-sound experiments that describe the effects and trends of these parameters for different populations of process models. Our results show that, indeed, there exist parameter configurations that have a significant positive impact on alignment computation efficiency.

AB - The aim of conformance checking is to assess whether a process model and event data, recorded in an event log, conform to each other. In recent years, alignments have proven extremely useful for calculating conformance statistics. Computing optimal alignments is equivalent to solving a shortest path problem on the state space of the synchronous product net of a process model and event data. State-of-the-art alignment based conformance checking implementations exploit the -algorithm, a heuristic search method for shortest path problems, and include a wide range of parameters that likely influence their performance. In previous work, we presented a preliminary and exploratory analysis of the effect of these parameters. This paper extends the aforementioned work by means of large-scale statistically-sound experiments that describe the effects and trends of these parameters for different populations of process models. Our results show that, indeed, there exist parameter configurations that have a significant positive impact on alignment computation efficiency.

KW - Alignments

KW - Conformance checking

KW - Process mining

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

U2 - 10.1007/978-3-662-58381-4_1

DO - 10.1007/978-3-662-58381-4_1

M3 - Chapter

AN - SCOPUS:85057200177

SN - 978-3-662-58380-7

SN - 978-3-662-58381-4

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

SP - 1

EP - 26

BT - Transactions on Petri Nets and Other Models of Concurrency XIII

A2 - Koutny, Maciej

A2 - Kristensen, Lars Michael

A2 - Penczek, Wojciech

PB - Springer

CY - Berlin

ER -

van Zelst SJ, Bolt A, van Dongen BF. Computing alignments of event data and process models. In Koutny M, Kristensen LM, Penczek W, editors, Transactions on Petri Nets and Other Models of Concurrency XIII. Berlin: Springer. 2018. p. 1-26. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-662-58381-4_1