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

    8 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
    Conference number: 16

    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)
    Abbreviated titleBPM 2018
    OtherDissertation Award, Demonstration, and Industrial Track at BPM
    Internet address


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

    Cite this