Efficient Alignment Between Event Logs and Process Models

Wei Song, Xiaoxu Xia, Hans Arno Jacobsen, Pengcheng Zhang, Hao Hu

Research output: Contribution to journalArticlepeer-review

46 Scopus citations


The aligning of event logs with process models is of great significance for process mining to enable conformance checking, process enhancement, performance analysis, and trace repairing. Since process models are increasingly complex and event logs may deviate from process models by exhibiting redundant, missing, and dislocated events, it is challenging to determine the optimal alignment for each event sequence in the log, as this problem is NP-hard. Existing approaches utilize the cost-based A∗ algorithm to address this problem. However, scalability is often not considered, which is especially important when dealing with industrial-sized problems. In this paper, by taking advantage of the structural and behavioral features of process models, we present an efficient approach which leverages effective heuristics and trace replaying to significantly reduce the overall search space for seeking the optimal alignment. We employ real-world business processes and their traces to evaluate the proposed approach. Experimental results demonstrate that our approach works well in most cases, and that it outperforms the state-of-the-art approach by up to 5 orders of magnitude in runtime efficiency.

Original languageEnglish
Article number7546937
Pages (from-to)136-149
Number of pages14
JournalIEEE Transactions on Services Computing
Issue number1
StatePublished - 1 Jan 2017
Externally publishedYes


  • alignment
  • Event logs
  • process decomposition
  • process models
  • trace replaying
  • trace segmentation


Dive into the research topics of 'Efficient Alignment Between Event Logs and Process Models'. Together they form a unique fingerprint.

Cite this