MaxSync-BPM2018

Maximizing Synchronization for Aligning Observed and Modelled Behaviour

This repository hosts the results for the paper.

Please note that all experiments in the paper were performed on an Intel Core^TM i7-4710MQ processor with 2.50GHz and 7.4Gib memory, running Debian Stretch.

Submitted and accepted at BPM 2018.

Authors:

• Formal Methods and Tools, University of Twente, The Netherlands

  • Vincent Bloemen*: [email protected]
  • Jaco van de Pol: [email protected]

• Eindhoven University of Technology, Eindhoven, The Netherlands

  • Sebastiaan van Zelst: [email protected]
  • Boudewijn van Dongen: [email protected]

• Process and Data Science, RWTH Aachen University, Germany

  • Wil van der Aalst: [email protected]

* Supported by the 3TU.BSR project.

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.

Implementation

The implementation for A* and the transitive closure graph algorithm are available in ProM 6.8 toolset (the transitive closure graph algorithm is implemented in the MaxSyncAlignments package).

The source code and installation instructions for the Symbolic alignment algorithm is obtained from https://github.com/utwente-fmt/SymbolicAlign-ACSD18.

If you experience any issues with the installation please consult the LTSmin website for further instructions. Otherwise, or if you would like help to repeat the experiments please contact the first author (Vincent Bloemen) for further help.

Data

All data used in the paper is available at the 4TU data centre: https://doi.org/10.4121/uuid:5f168a76-cc26-42d6-a67d-48be9c978309.