Abstract

A process model is a graphical representation of the actual business process that is being executed. To build a process model from an event log, process discovery algorithms are used which are complex in nature and require prolonged execution as they involve extraction of the various ordering relations that exist between the events present in that event log. Given the exponential increase of data in event log, it is significant to have a robust and effective implementation of the computation intensive process discovery algorithms through parallel computing to generate a process model. Motivated by this theme the present work proposes a parallel computing approach to implement the Alpha algorithm for process discovery using the OpenMP application programming interface (API). An appropriate parallel programming framework to reduce the execution time by exploiting parallelism at the level of data, as well as task through a thorough analysis of the steps involved in the Alpha algorithm, has been developed. The effectiveness of the developed approach is presented on the basis of speedup factor through several experiments. The highest and the lowest speedups achieved were 13.24x and 4.71x respectively.

Keyword

Process model discovery, Alpha algorithm, OpenMP, Speedup.

Cite this article

Sahu M, Nayak GK

Refference

[1][1]Van Der Aalst W, Weijters T, Maruster L. Workflow mining: discovering process models from event logs. IEEE Transactions on Knowledge & Data Engineering. 2004; 16(9):1128-42.

[2][2]Kindler E, Rubin V, Schäfer W. Process mining and petri net synthesis. In international conference on business process management 2006 (pp. 105-16). Springer, Berlin, Heidelberg.

[3][3]Bergenthum R, Desel J, Lorenz R, Mauser S. Process mining based on regions of languages. In international conference on business process management 2007 (pp. 375-83). Springer, Berlin, Heidelberg.

[4][4]Motahari-Nezhad HR, Saint-Paul R, Benatallah B, Casati F. Deriving protocol models from imperfect service conversation logs. IEEE Transactions on Knowledge and Data Engineering. 2008; 20(12):1683-98.

[5][5]Bergenthum R, Desel J, Mauser S, Lorenz R. Construction of process models from example runs. In transactions on petri nets and other models of concurrency II 2009 (pp. 243-59). Springer, Berlin, Heidelberg.

[6][6]Solé M, Carmona J. Region-based foldings in process discovery. IEEE Transactions on Knowledge and Data Engineering. 2013; 25(1):192-205.

[7][7]Van Dongen BF, De Medeiros AA, Wen L. Process mining: overview and outlook of petri net discovery algorithms. In transactions on petri nets and other models of concurrency II 2009 (pp. 225-42). Springer, Berlin, Heidelberg.

[8][8]Günther CW, Rozinat A. Disco: discover your processes. BPM (Demos). 2012; 940:40-4.

[9][9]Huang Z, Kumar A. A study of quality and accuracy trade-offs in process mining. INFORMS Journal on Computing. 2012; 24(2):311-27.

[10][10]Guo Q, Wen L, Wang J, Yan Z, Philip SY. Mining invisible tasks in non-free-choice constructs. In international conference on business process management 2015 (pp. 109-25). Springer, Cham.

[11][11]Verbeek HM, Van Der Aalst WM, Munoz-Gama J. Divide and conquer: a tool framework for supporting decomposed discovery in process mining. The Computer Journal. 2017; 60(11):1649-74.

[12][12]Van DerWerf JM, Van Dongen BF, Hurkens CA, Serebrenik A. Process discovery using integer linear programming. Fundamenta Informaticae. 2009; 94(3-4):387-412.

[13][13]Van Zelst SJ, Van Dongen BF, Van Der Aalst WM, Verbeek HM. Discovering workflow nets using integer linear programming. Computing. 2018; 100(5):529-56.

[14][14]Van Zelst SJ, Van Dongen BF, Van Der Aalst WM. Avoiding over-fitting in ILP-based process discovery. In international conference on business process management 2016 (pp. 163-71). Springer, Cham.

[15][15]Van Zelst SJ, Van Dongen BF, Van Der Aalst WM. ILP-based process discovery using hybrid regions. In ATAED@ petri nets/ACSD 2015 (pp. 47-61).

[16][16]Breuker D, Matzner M, Delfmann P, Becker J. Comprehensible predictive models for business processes. MIS Quarterly. 2016.

[17][17]Breuker D, Delfmann P, Matzner M, Becker J. Designing and evaluating an interpretable predictive modeling technique for business processes. In international conference on business process management 2014 (pp. 541-53). Springer, Cham.

[18][18]Song W, Jacobsen HA, Ye C, Ma X. Process discovery from dependence-complete event logs. IEEE Transactions on Services Computing. 2016; 9(5):714-27.

[19][19]Carmona J, Cortadella J. Process discovery algorithms using numerical abstract domains. IEEE Transactions on Knowledge and Data Engineering. 2014; 26(12):3064-76.

[20][20]Tapia-Flores T, Rodriguez-Perez E, Lopez-Mellado E. Discovering process models from incomplete event logs using conjoint occurrence classes. In ATAED@ petri nets/ACSD 2016 (pp. 31-46).

[21][21]Li C, Ge J, Huang L, Hu H, Wu B, Yang H, et al. Process mining with token carried data. Information Sciences. 2016; 328:558-76.

[22][22]Greco G, Guzzo A, Lupia F, Pontieri L. Process discovery under precedence constraints. ACM Transactions on knowledge discovery from data. 2015; 9(4).

[23][23]Vazquez-Barreiros B, Mucientes M, Lama M. ProDiGen: mining complete, precise and minimal structure process models with a genetic algorithm. Information Sciences. 2015; 294:315-33.

[24][24]Vazquez-Barreiros B, Mucientes M, Lama M. A genetic algorithm for process discovery guided by completeness, precision and simplicity. In international conference on business process management 2014 (pp. 118-33). Springer, Cham.

[25][25]Nguyen H, Dumas M, Ter Hofstede AH, La Rosa M, Maggi FM. Mining business process stages from event logs. In international conference on advanced information systems engineering 2017 (pp. 577-94). Springer, Cham.

[26][26]Van Eck ML, Sidorova N, Van Der Aalst WM. Discovering and exploring state-based models for multi-perspective processes. In international conference on business process management 2016 (pp. 142-57). Springer, Cham.

[27][27]Van Eck ML, Sidorova N, Van Der Aalst WM. Guided interaction exploration in artifact-centric process models. IEEE conference on business informatics 2017 (109-18). IEEE.

[28][28]Conforti R, Dumas M, Garcia-Banuelos L, La Rosa M. Beyond tasks and gateways: discovering BPMN models with subprocesses, boundary events and activity markers. In international conference on business process management 2014 (pp. 101-17). Springer, Cham.

[29][29]Conforti R, Dumas M, García-Bañuelos L, La Rosa M. BPMN miner: automated discovery of BPMN process models with hierarchical structure. Information Systems. 2016; 56:284-303.

[30][30]Schonig S, Rogge-Solti A, Cabanillas C, Jablonski S, Mendling J. Efficient and customisable declarative process mining with SQL. In international conference on advanced information systems engineering 2016 (pp. 290-305). Springer, Cham.

[31][31]Schonig S, Di Ciccio C, Maggi FM, Mendling J. Discovery of multi-perspective declarative process models. In international conference on service-oriented computing 2016 (pp. 87-103). Springer, Cham.

[32][32]Augusto A, Conforti R, Dumas M, La Rosa M. Split miner: discovering accurate and simple business process models from event logs. International conference on data mining 2017 (pp. 1-10). IEEE.

[33][33]Weijters AJ, Van Der Aalst WM. Rediscovering workflow models from event-based data using little thumb. Integrated Computer-Aided Engineering. 2003; 10(2):151-62.

[34][34]Vanden Broucke SK, De Weerdt J. Fodina: a robust and flexible heuristic process discovery technique. Decision Support Systems. 2017; 100:109-18.

[35][35]De Weerdt J, Vanden Broucke SK, Caron F. Bidimensional process discovery for mining BPMN models. In international conference on business process management 2014 (pp. 529-40). Springer, Cham.

[36][36]Conforti R, La Rosa M, Ter Hofstede AH. Filtering out infrequent behavior from business process event logs. IEEE Transactions on Knowledge and Data Engineering. 2017; 29(2):300-14.

[37][37]Mannhardt F, De Leoni M, Reijers HA, Van Der Aalst WM. Data-driven process discovery-revealing conditional infrequent behavior from event logs. In international conference on advanced information systems engineering 2017 (pp. 545-60). Springer, Cham.

[38][38]Van Dongen B, Carmona J, Chatain T, Taymouri F. Aligning modeled and observed behavior: a compromise between computation complexity and quality. In international conference on advanced information systems engineering 2017 (pp. 94-109). Springer, Cham.

[39][39]Leemans M, Van der Aalst WM. Modeling and discovering cancelation behavior. In OTM confederated international conferences

[40][40]Leemans SJ, Fahland D, Van Der Aalst WM. Discovering block-structured process models from event logs containing infrequent behaviour. In international conference on business process management 2013 (pp. 66-78). Springer, Cham.

[41][41]Augusto A, Conforti R, Dumas M, La Rosa M, Bruno G. Automated discovery of structured process models from event logs: the discover-and-structure approach. Data & Knowledge Engineering. 2018; 117:373-92.

[42][42]Sahu M, Chakraborty R, Nayak G. A task-level parallelism approach for process discovery. International Journal of Engineering & Technology. 2018: 7(4):2446-52.

[43][43]Ciorba FM, Iwainsky C, Buder P. OpenMP loop scheduling revisited: making a case for more schedules. In international workshop on OpenMP 2018 (pp. 21-36). Springer, Cham.

[44][44]Van Der Aalst WM. Process mining: data science in action. Springer; 2016.

[45][45]Weijters AJ, Van Der Aalst WM, De Medeiros AA. Process mining with the heuristics miner-algorithm. Technische Universiteit Eindhoven, Tech. Rep. WP. 2006; 166:1-34.

[46][46]Weijters AJ, Ribeiro JT. Flexible heuristics miner (FHM). In symposium on computational intelligence and data mining 2011 (pp. 310-7). IEEE.

[47][47]Serrano MA, Royuela S, Quinones E. Towards an OpenMP specification for critical real-time systems. In international workshop on OpenMP 2018 (pp. 143-59). Springer, Cham.

[48][48]Pacheco P. An introduction to parallel programming. Elsevier; 2011.

[49][49]Kemp J, Chapman B. Mapping OpenMP to a distributed tasking runtime. In international workshop on OpenMP 2018 (pp. 222-35). Springer, Cham.

[50][50]Hennessy JL, Patterson DA. Computer architecture: a quantitative approach. Elsevier; 2011.