(Publisher of Peer Reviewed Open Access Journals)
Navigation

International Journal of Advanced Computer Research (IJACR)

ISSN (Print):2249-7277    ISSN (Online):2277-7970
Volume-9 Issue-41 March-2019
Full-Text PDF
Paper Title : An efficient parallel framework for process discovery using OpenMP
Author Name : Muktikanta Sahu and Gopal Krishna Nayak
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.
Keywords : Process model discovery, Alpha algorithm, OpenMP, Speedup.
Cite this article : Sahu M, Nayak GK. An efficient parallel framework for process discovery using OpenMP. International Journal of Advanced Computer Research. 2019; 9(41):112-123. DOI:10.19101/IJACR.2018.839057.
References :
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[6]Solé M, Carmona J. Region-based foldings in process discovery. IEEE Transactions on Knowledge and Data Engineering. 2013; 25(1):192-205.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[8]Günther CW, Rozinat A. Disco: discover your processes. BPM (Demos). 2012; 940:40-4.
[Google Scholar]
[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.
[Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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).
[Google Scholar]
[16]Breuker D, Matzner M, Delfmann P, Becker J. Comprehensible predictive models for business processes. MIS Quarterly. 2016.
[Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[19]Carmona J, Cortadella J. Process discovery algorithms using numerical abstract domains. IEEE Transactions on Knowledge and Data Engineering. 2014; 26(12):3064-76.
[Crossref] [Google Scholar]
[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).
[Google Scholar]
[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.
[Crossref] [Google Scholar]
[22]Greco G, Guzzo A, Lupia F, Pontieri L. Process discovery under precedence constraints. ACM Transactions on knowledge discovery from data. 2015; 9(4).
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[34]Vanden Broucke SK, De Weerdt J. Fodina: a robust and flexible heuristic process discovery technique. Decision Support Systems. 2017; 100:109-18.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[39]Leemans M, Van der Aalst WM. Modeling and discovering cancelation behavior. In OTM confederated international conferences
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[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]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.
[Crossref] [Google Scholar]
[44]Van Der Aalst WM. Process mining: data science in action. Springer; 2016.
[Google Scholar]
[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.
[Google Scholar]
[46]Weijters AJ, Ribeiro JT. Flexible heuristics miner (FHM). In symposium on computational intelligence and data mining 2011 (pp. 310-7). IEEE.
[Crossref] [Google Scholar]
[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.
[Crossref] [Google Scholar]
[48]Pacheco P. An introduction to parallel programming. Elsevier; 2011.
[Google Scholar]
[49]Kemp J, Chapman B. Mapping OpenMP to a distributed tasking runtime. In international workshop on OpenMP 2018 (pp. 222-35). Springer, Cham.
[Crossref] [Google Scholar]
[50]Hennessy JL, Patterson DA. Computer architecture: a quantitative approach. Elsevier; 2011.
[Google Scholar]