Proceedings of ISP RAS

Applying MapReduce to Conformance Checking

I.S. Shugurov (HSE, Moscow, Russia)
A.A. Mitsyuk (HSE, Moscow, Russia)


Process mining is a relatively new research field, offering methods of business processes analysis and improvement, which are based on studying their execution history (event logs). Conformance checking is one of the main sub-fields of process mining. Conformance checking algorithms are aimed to assess how well a given process model, typically represented by a Petri net, and a corresponding event log fit each other. Alignment-based conformance checking is the most advanced and frequently used type of such algorithms.  This paper deals with the problem of high computational complexity of the alignment-based conformance checking algorithm. Currently, alignment-based conformance checking is quite inefficient in terms of memory consumption and time required for computations. Solving this particular problem is of high importance for checking conformance between real-life business process models and event logs, which might be quite problematic using existing approaches. MapReduce is a popular model of parallel computing which allows for simple implementation of efficient and scalable distributed calculations. In this paper, a MapReduce version of the alignment-based conformance checking algorithm is described and evaluated. We show that conformance checking can be distributed using MapReduce and can benefit from it. Moreover, it is demonstrated that computation time scales linearly with the growth of event log size


process mining, conformance checking, MapReduce, Hadoop, big data


Proceedings of the Institute for System Programming, vol. 28, issue 3, 2016, pp. 103-122.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2016-28(3)-7

For citation

I.S. Shugurov, A.A. Mitsyuk Applying MapReduce to Conformance Checking. Proceedings of the Institute for System Programming, vol. 28, issue 3, 2016, pp. 103-122. DOI: 10.15514/ISPRAS-2016-28(3)-7.

Full text of the paper in pdf Back to the contents of the volume