This post has been authored by Tsung-Hao Huang.
Process discovery is a cornerstone of process mining, enabling organizations to uncover the behaviors hidden in their event logs and transform them into actionable process models. While many algorithms exist, few balance between scalability and providing sound, free-choice workflow nets. The Synthesis Miner [1] is one of the algorithms that guarantee these desirable properties while also supporting non-block structures. However, scalability issues have posed challenges for its widespread adoption in real-world applications.
In our recent work [2], we introduced two extensions to address the bottlenecks in the Synthesis Miner’s computation. By leveraging log heuristics and isolating minimal subnets, these extensions reduce the search space and break down generation and evaluation tasks into smaller, more manageable components. The results speak for themselves: our experiments show an average 82.85% reduction in computation time without compromising model quality.
Log heuristics help pinpoint the most likely positions for modifications, reducing the number of nodes and transitions considered for connection. Meanwhile, minimal subnet extraction isolates only the relevant parts of the process model, enabling faster candidate generation and conformance checking. Together, these improvements streamline the process discovery workflow, making it more feasible to apply the Synthesis Miner to larger, real-life event logs.
This work highlights how targeted optimizations can unlock the potential of advanced algorithms in process mining. By addressing scalability challenges, we hope to make tools like the Synthesis Miner more accessible for practical use cases, bridging the gap between process theory and business applications.
[1] Huang, TH., van der Aalst, W.M.P. (2022). Discovering Sound Free-Choice Workflow Nets with Non-block Structures. In: Almeida, J.P.A., Karastoyanova, D., Guizzardi, G., Montali, M., Maggi, F.M., Fonseca, C.M. (eds) Enterprise Design, Operations, and Computing. EDOC 2022. Lecture Notes in Computer Science, vol 13585. Springer, Cham. https://doi.org/10.1007/978-3-031-17604-3_12
[2] Huang, TH., Schneider, E., Pegoraro, M., van der Aalst, W.M.P. (2024). Fast & Sound: Accelerating Synthesis-Rules-Based Process Discovery. In: van der Aa, H., Bork, D., Schmidt, R., Sturm, A. (eds) Enterprise, Business-Process and Information Systems Modeling. BPMDS EMMSAD 2024 2024. Lecture Notes in Business Information Processing, vol 511. Springer, Cham. https://doi.org/10.1007/978-3-031-61007-3_20