Efficient Alignment Between Event Logs and Process Models

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

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

46 Zitate (Scopus)


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.

Seiten (von - bis)136-149
FachzeitschriftIEEE Transactions on Services Computing
PublikationsstatusVeröffentlicht - 1 Jan. 2017
Extern publiziertJa


Untersuchen Sie die Forschungsthemen von „Efficient Alignment Between Event Logs and Process Models“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren