Enhancing the Applicability of the eST-Miner: Efficient Precision-Guided Implicit Place Avoidance

In process discovery, we aim to find a model that describes the underlying process best, given an event log. The eST-Miner is a discovery technique inspired by language-based regions. It discovers precise Petri nets containing exactly one transition for each activity in the event log by efficiently traversing the space of all possible places. It then expands the model iteratively with places. The final model consists of the maximal set of places considered fitting with respect to a user-definable fraction of the behavior in the log evaluated by token-based replay. Therefore, the eST-Miner can derive complex control-flow structures that other approaches fail to discover and handle noise and infrequent behavior. Although the eST-Miner discovers high-quality models, its feasibility has previously been limited by its runtime: When naively inserting places, the discovered models contain many implicit places, i.e., places whose removal does not change its language and is time-consuming. Therefore, we propose an efficient strategy that avoids adding implicit places by exploiting log information while including non-fitting log traces. We extend the discovery with information on the precision of the (expanding) model based on escaping edges. With our extensions, the eST-Miner becomes a competitive choice among other process discovery techniques. We demonstrate the effectiveness of our heuristics using the eST-Miner as an exemplary use case and run various experiments on real-life and artificial event logs.