Extending Graph-Based Process Discovery for Hierarchical Block Detection and Incomplete Concurrent Relationship Handling

Abstract

The flow of business process activities in an organization can run simply in the form of sequential or complex in the form of choice and parallel. In the discovery process, parallel conditions can be deduced from the concurrent flows between activities. Concurrent patterns can be identified by tracing pairs of sequences in opposite directions between two activities. Long parallel blocks allow incomplete concurrent relationship (ICR) phenomena when the observed data only provides a one-way sequence flow against conditions that should be concurrent. All state-of-the-art algorithms starting from Graph-based Process Discovery (GPD), Inductive Miner (IM), and Split Miner (SM), detect ICR as a sequence so that the quality of the resulting model decreases. This paper proposes the GPD++ algorithm for block detection of complex structures by combining algorithms from GPD and SM and handling ICR for each detected parallel block. The experiment compared IM, SM, and GPD++ using real-life data from the container loading and unloading process during import activities and some public data. The experimental results show that only GPD++ has successfully detected and corrected ICR to obtain the best fitness and precision values. In addition, GPD++ is also the only algorithm that can find hierarchies in the same type of complex structure, resulting in a block model with consistent split-join pairs.

Keywords

• Graph-based process discovery
• graph database
• incomplete concurrent relationship
• block hierarchy
• GPD++