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

    6 Citations (Scopus)


    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
    Number of pages17
    ISBN (Electronic)978-3-319-98648-7
    ISBN (Print)978-3-319-98647-0
    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


    Conference16th International Conference on Business Process Management, BPM 2018

    Fingerprint Dive into the research topics of 'Maximizing synchronization for aligning observed and modelled behaviour'. Together they form a unique fingerprint.

    Cite this