A task-level parallelism approach for process discovery

 
 
 
  • Abstract
  • Keywords
  • References
  • PDF
  • 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.


  • Keywords


    Alpha algorithm; MPI; Process Discovery; Process Mining; Speedup.

  • References


      [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).


 

View

Download

Article ID: 14748
 
DOI: 10.14419/ijet.v7i4.14748




Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.