Fast & Sound: Accelerating Synthesis-Rules-Based Process Discovery

Process discovery aims to construct process models describing the observed behaviors of information systems. It is an essential step in process mining projects as most process mining techniques assume a process model as input. While various process discovery algorithms exist, few provide desirable properties: soundness and free-choiceness. By exploiting the free-choice net theory, the recently developed Synthesis Miner not only guarantees the two desirable properties but also enables a more flexible representation (non-block structures) of the discovered process models. The flexibility allows the Synthesis Miner to discover process models with potentially higher quality. Nevertheless, applying the Synthesis Miner remains a challenge due to its lack of scalability. In this paper, we identify the bottleneck and address it by introducing various extensions that utilize the log heuristics and extract the minimal sub-net of the process model. The evaluation using real-life event logs shows that the proposed extensions improve the scalability of the Synthesis Miner by reducing the computation time by 82.85% on average.