A task-level parallelism approach for process discovery

  • Authors

    • Muktikanta Sahu International Institute of Information Technology Bubaneswar
    • Rupjit Chakraborty International Institute of Information Technology Bubaneswar
    • Gopal Krishna Nayak International Institute of Information Technology Bubaneswar
    2018-09-20
    https://doi.org/10.14419/ijet.v7i4.14748
  • Alpha algorithm, MPI, Process Discovery, Process Mining, Speedup.

  • Abstract

    Building process models from the available data in the event logs is the primary objective of Process discovery. Alpha algorithm is one of the popular algorithms accessible for ascertaining a process model from the event logs in process mining. The steps involved in the Alpha algorithm are computationally rigorous and this problem further manifolds with the exponentially increasing event log data. In this work, we have exploited task parallelism in the Alpha algorithm for process discovery by using MPI programming model. The proposed work is based on distributed memory parallelism available in MPI programming for performance improvement. Independent and computationally intensive steps in the Alpha algorithm are identified and task parallelism is exploited. The execution time of serial as well as parallel implementation of Alpha algorithm are measured and used for calculating the extent of speedup achieved. The maximum and minimum speedups obtained are 3.97x and 3.88x respectively with an average speedup of 3.94x.

  • References

    1. [1] Wil MP van der Aalst, Process Mining, Springer, (2011).

      [2] Wil MP van der Aalst, “Process mining: Overview and opportunitiesâ€, ACM Transactions on Management Information Systems (TMIS), Vol.3, No.2, (2012), p.7.

      [3] W. Aalst, A. Adriansyah, A. K. A. Medeiros, F. Arcieri, T. Baier, T. Blickle, J. C. Bose, P. Brand, R. Brandtjen, J. Buijs et al, “Process mining manifestoâ€, Business process management workshops, Springer (2012), pp.169-194.

      [4] W. Van der Aalst, T. Weijters, and L. Maruster, “Workflow mining: Discovering process models from event logsâ€, IEEE Transactions on Knowledge and Data Engineering, Vol.16, No.9, (2004), p.1128-1142.

      [5] T. Andrews, S. Qadeer, S. K. Rajamani, J. Rehof, and Y. Xie, “Zing: A model checker for concurrent softwareâ€, in International Conference on Computer Aided Verification, Springer (2004), pp.484-487.

      [6] A. Weijters, W. M. van Der Aalst, and A. A. De Medeiros, “Process mining with the heuristics miner-algorithmâ€, Technische Universiteit Eindhoven, Tech. Rep. WP, Vol.166, (2006), pp.1-34.

      [7] L. Wen, W. M. van der Aalst, J. Wang, and J. Sun, “Mining process models with non-free-choice constructsâ€, Data Mining and Knowledge Discovery, vol. 15, no.2, (2007), pp. 145–180.

      [8] G. Schimm, “Mining exact models of concurrent workflowsâ€, Computers in Industry, vol.53, no.3, (2004), pp.265–281.

      [9] W. M. Van Der Aalst, V. Rubin, H. M. Verbeek, B. F. van Dongen, E. Kindler, and C. W. G¨unther, “Process mining: a two-step approach to balance between underfitting and overfittingâ€, Software and Systems Modeling, vol.9, no. 1, (2010), pp.87–111.

      [10] R. Bergenthum, J. Desel, R. Lorenz, and S. Mauser, “Process mining based on regions of languagesâ€, in International Conference on Business Process Management. Springer(2007), pp.375–383.

      [11] D. R. Ferreira and D. Gillblad, “Discovering process models from unlabeled event logsâ€, in International Conference on Business Process Management. Springer(2009), pp.143–158.

      [12] W. M. Van der Aalst and A. Weijters, “Process mining: a research agendaâ€, Computers in industry, vol. 53, no.3, (2004), pp.231–244.

      [13] A. K. de MEDEIROS, A. J. Weijters, and W. M. van der Aalst, “Genetic process mining: an experimental evaluationâ€, Data Mining and Knowledge Discovery, vol.14, no.2, (2007), pp.245–304.

      [14] C. J. Turner, A. Tiwari, and J. Mehnen, “A genetic programming approach to business process miningâ€, in Proceedings of the 10th annual conference on Genetic and evolutionary computation. ACM(2008), pp.1307–1314.

      [15] G. Greco, A. Guzzo, L. Pontieri, and D. Sacca, “Discovering expressive process models by clustering log tracesâ€, IEEE Transactions on Knowledge and Data Engineering, vol.18, no.8, (2006), pp.1010–1027.

      [16] M. Song, C.W. G¨unther, andW. M. Aalst, “Trace clustering in process miningâ€, in Business Process Management Workshops. Springer(2009), pp.109–120.

      [17] R. J. C. Bose and W. M. van der Aalst, “Context aware trace clustering: Towards improving process mining resultsâ€, in Proceedings of the 2009 SIAM International Conference on Data Mining. SIAM(2009), pp.401–412.

      [18] B. F. van Dongen and A. Adriansyah, “Process mining: fuzzy clustering and performance visualizationâ€, in International Conference on Business Process Management. Springer(2009), pp.158–169.

      [19] C.W. G¨unther, A. Rozinat, andW. M. Van Der Aalst, “Activity mining by global trace segmentationâ€, in International Conference on Business Process Management. Springer(2009), pp.128–139.

      [20] C. W. G¨unther and W. M. Van Der Aalst, “Fuzzy mining–adaptive process simplification based on multi-perspective metricsâ€, in International Conference on Business Process Management. Springer(2007), pp.328–343.

      [21] S. Goedertier, D. Martens, J. Vanthienen, and B. Baesens, “Robust process discovery with artificial negative eventsâ€, Journal of Machine Learning Research, vol.10, no.Jun, (2009), pp.1305–1340.

      [22] L. V. Allen and D. M. Tilbury, “Anomaly detection using model generation

      for event-based systems without a preexisting formal modelâ€, IEEE Transactions on Systems, Man, and Cybernetics-Part A:Systems and Humansâ€, vol.42, no.3, (2012), pp. 654–668.

      [23] S. X. Sun, Q. Zeng, and H.Wang, “Process-mining-based workflow model fragmentation for distributed executionâ€, IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, vol.41, no.2, (2011), pp.294–310.

      [24] W. M. Van Der Aalst, “Decomposing process mining problems using passagesâ€, in International Conference on Application and Theory of Petri Nets and Concurrency. Springer(2012), pp.72–91.

      [25] W. M. Van der Aalst, “Decomposing petri nets for process mining: A generic approachâ€, Distributed and Parallel Databases, vol.31, no.4, (2013), pp. 471–507.

      [26] ——, “Process mining in the large: a tutorialâ€, in Business Intelligence. Springer(2014), pp. 33–76.

      [27] W. M. Van Der Aalst, “A general divide and conquer approach for process miningâ€, in Computer Science and Information Systems (Fed-CSIS), Federated Conference on. IEEE(2013), pp.1–10.

      [28] A. Burattin, A. Sperduti, and W. M. van der Aalst, “Heuristics miners for streaming event dataâ€, arXiv preprint arXiv:1212.6383, (2012).

      [29] M. L. van Eck, N. Sidorova, and W. M. van der Aalst, “Discovering and exploring state-based models for multi-perspective processesâ€, in International Conference on Business Process Management. Springer(2016), pp.142–157.

      [30] W.M. van der Aalst, A. Kalenkova, V. Rubin, and E. Verbeek, “Process discovery using localized eventsâ€, in International Conference on Applications and Theory of Petri Nets and Concurrency. Springer(2015), pp.287–308.

      [31] M. Leemans andW. M. van der Aalst, “Process mining in software systems: discovering real-life business transactions and process models from distributed systemsâ€, in Model Driven Engineering Languages and Systems (MODELS), 2015 ACM/IEEE 18th International Conference on. IEEE(2015), pp.44–53.

      [32] W. M. Van der Aalst, “The application of petri nets to workflow managementâ€,

      Journal of circuits, systems, and computers, vol.8, no.01, (1998), pp.21–66.

      [33] R. Brightwell and K. Underwood, “Evaluation of an eager protocol optimization for mpiâ€, in European Parallel Virtual Machine/Message Passing Interface Users Group Meeting. Springer(2003), pp.327–334.

      [34] D. Buntinas, G. Mercier, and W. Gropp, “Implementation and evaluation of shared-memory communication and synchronization operations in mpich2 using the nemesis communication subsystemâ€, Parallel Computing, vol.33, no. 9, (2007), pp. 634–644.

      [35] P. Pacheco, An introduction to parallel programming. Elsevier, (2011).

      [36] L. John, Hennessy and david a. patterson, Computer architecture a quantitative approach, The Morgan Kaufmann Series in Computer Architecture and Design, (2003).

  • Downloads

  • How to Cite

    Sahu, M., Chakraborty, R., & Nayak, G. K. (2018). A task-level parallelism approach for process discovery. International Journal of Engineering & Technology, 7(4), 2446-2452. https://doi.org/10.14419/ijet.v7i4.14748

    Received date: 2018-06-28

    Accepted date: 2018-09-04

    Published date: 2018-09-20