Applying MapReduce to Conformance Checking
https://doi.org/10.15514/ISPRAS-2016-28(3)-7
Abstract
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.
About the Authors
I. S. Shugurov
National Research University Higher School of Economics
Russian Federation
Russian Federation
A. A. Mitsyuk
National Research University Higher School of Economics
Russian Federation
Russian Federation
References
1. Wil M. P. van der Aalst, Process mining: discovery, conformance and enhancement of business processes. Springer, 2011. C. Lattner. LLVM: An Infrastructure for Multi-Stage Optimization. Master’s thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL.
2. S. A. Shershakov and V. A. Rubin, “System runs analysis with process mining,” Modeling and Analysis of Information Systems, vol. 22, no. 6, pp. 818–833, December 2015.
3. S. A. Shershakov, “VTMine framework as applied to process mining modeling,” International Journal of Computer and Communication Engineering, vol. 4, no. 3, pp. 166–179, May 2015.
4. W. M. van der Aalst, “Process Mining in the Large: A Tutorial,” in Business Intelligence. Springer, 2014, pp. 33–76.
5. C. Bratosin, N. Sidorova, and W. van der Aalst, “Distributed Genetic Process Mining,” in Evolutionary Computation (CEC), 2010 IEEE Congress on, 2010, pp. 1–8.
6. S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst, “Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour,” in Business Process Management Workshops, ser. Lecture Notes in Business Information Processing, N. Lohmann, M. Song, and P. Wohed, Eds. Springer International Publishing, 2014, vol. 171, pp. 66–78.
7. A. A. Kalenkova, I. A. Lomazova, and W. M. P. van der Aalst, “Process Model Discovery: A Method Based on Transition System Decomposition,” in Petri Nets, ser. Lecture Notes in Computer Science, vol. 8489. Springer, 2014, pp. 71–90.
8. D. Fahland and W. M. P. van der Aalst, “Model Repair - Aligning Process Models to Reality,” Inf. Syst., vol. 47, pp. 220–243, 2015. [Online]. Available: http://dx.doi.org/10.1016/j.is.2013.12.007
9. I. S. Shugurov and A. A. Mitsyuk, “Iskra: A Tool for Process Model Repair,” Proceedings of the Institute for System Programming, vol. 27, no. 3, pp. 237–254, 2015.
10. J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, 2008. [Online]. Available: http://doi.acm.org/10.1145/1327452.1327492
11. W. M. P. van der Aalst, “Distributed Process Discovery and Conformance Checking,” in Fundamental Approaches to Software Engineering, ser. Lecture Notes in Computer Science, J. de Lara and A. Zisman, Eds. Springer Berlin Heidelberg, 2012, vol. 7212, pp. 1–25.
12. A. Adriansyah, “Aligning Observed and Modeled Behavior,” PhD Thesis, Technische Universiteit Eindhoven, Eindhoven, The Netherlands, 2014.
13. A. Adriansyah, B. van Dongen, and W. M. van der Aalst, “Conformance Checking using Cost-Based Fitness Analysis,” in IEEE International Enterprise Computing Conference (EDOC 2011), C. Chi and P. Johnson, Eds. IEEE Computer Society, 2011, pp. 55–64.
14. D. Miner and A. Shook, MapReduce Design Patterns: Building Effective Algorithms and Analytics for Hadoop and Other Systems, 1st ed. O’Reilly Media, Inc., 2012.
15. W. M. P. van der Aalst, “Decomposing Petri Nets for Process Mining: A Generic Approach,” Distributed and Parallel Databases, vol. 31, no. 4, pp. 471–507, 2013.
16. J. Munoz-Gama, “Conformance checking and diagnosis in process mining,” PhD Thesis, Universitat Politecnica de Catalunya, 2014.
17. W. M. P. van der Aalst, “Decomposing Process Mining Problems Using Passages,” in Application and Theory of Petri Nets, ser. Lecture Notes in Computer Science, S. Haddad and L. Pomello, Eds. Springer Berlin Heidelberg, 2012, vol. 7347, pp. 72–91.
18. J. Munoz-Gama, J. Carmona, and W. M. van der Aalst, “Single-Entry Single-Exit Decomposed Conformance Checking,” Information Systems, vol. 46, pp. 102–122, 2014.
19. “Apache hadoop,” http://hadoop.apache.org/, accessed: 2016-04-01.
20. W. M. P. van der Aalst and. B. van Dongen, C. Gunther, A. Rozinat, ¨ E. Verbeek, and T. Weijters, “ProM: The Process Mining Toolkit,” in Business Process Management Demonstration Track (BPMDemos 2009), ser. CEUR Workshop Proceedings, A. Medeiros and B. Weber, Eds., vol. 489. CEUR-WS.org, 2009, pp. 1–4.
21. “Prom framework,” http://www.promtools.org/doku.php, accessed: 2016-04-01.
22. IEEE Task Force on Process Mining, “XES Standard Definition,” www.xes-standard.org, 2013.
23. “Apache mahout,” http://mahout.apache.org/, accessed: 2016-04-01.
24. “Amazon EMR,” https://aws.amazon.com/ru/elasticmapreduce/, accessed: 2016-04-01.
25. W. M. P. van der Aalst, A. H. M. ter Hofstede, B. Kiepuszewski, and A. P. Barros, “Workflow Patterns,” Distrib. Parallel Databases, vol. 14, no. 1, pp. 5–51, Jul. 2003. [Online]. Available: http: //dx.doi.org/10.1023/A:1022883727209
26. I. S. Shugurov and A. A. Mitsyuk, “Generation of a Set of Event Logs with Noise,” in Proceedings of the 8th Spring/Summer Young Researchers Colloquium on Software Engineering (SYRCoSE 2014), 2014, pp. 88–95.
27. H. Reguieg, F. Toumani, H. R. Motahari-Nezhad, and B. Benatallah, “Using MapReduce to Scale Events Correlation Discovery for Business Processes Mining,” in Business Process Management. Springer, 2012, pp. 279–284.
28. J. Evermann, “Scalable Process Discovery using Map-Reduce,” IEEE Transactions on Services Computing, vol. PP, no. 99, pp. 1–1, 2014.
29. J. Evermann and G. Assadipour, “Big Data meets Process Mining: Implementing the Alpha Algorithm with Map-Reduce,” in Proceedings of the 29th Annual ACM Symposium on Applied Computing. ACM, 2014, pp. 1414–1416.
30. W. M. P. van der Aalst, A. J. M. M. Weijters, and L. Maruster, “Workflow Mining: Discovering Process Models from Event Logs,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1128–1142, 2004.
31. A. J. M. M. Weijters and J. T. S. Ribeiro, “Flexible Heuristics Miner (FHM),” in Computational Intelligence and Data Mining (CIDM), 2011 IEEE Symposium on, April 2011, pp. 310–317.
32. S. Hernandez, S. Zelst, J. Ezpeleta, and W. M. P. van der Aalst, “Handling big (ger) logs: Connecting ProM 6 to Apache Hadoop,” in Proceedings of the BPM2015 Demo Session, ser. CEUR Workshop Proceedings, vol. 1418, 2015, pp. 80–84.
33. S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst, “Discovering Block-Structured Process Models from Incomplete Event Logs,” in Application and Theory of Petri Nets and Concurrency, ser. Lecture Notes in Computer Science, G. Ciardo and E. Kindler, Eds. Springer.
34.
Review
For citations:
Shugurov I.S., Mitsyuk A.A. Applying MapReduce to Conformance Checking. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2016;28(3):103-122. https://doi.org/10.15514/ISPRAS-2016-28(3)-7
Email this article 