Model-based trace variant analysis of event logs. Issue 102 (December 2021) - Boltenhagen, Mathilde; Chatain, Thomas; Carmona, Josep
Abstract: The comparison of trace variants of business processes opens the door for a fine-grained analysis of the distinctive features inherent in the executions of a process in an organization. The current approaches for trace variant analysis do not consider the situation where a process model is present, and therefore, it can guide the derivation of the trace variants by considering high-level structures present in the process model. In this paper we propose a fresh alternative to trace variant analysis, which proposes a generalized notion of trace variant that incorporates concurrency and iteration. This way, the analyst may be relieved from analyzing trace variants that are essentially the same, if these aspects are disregarded. We propose a general algorithm for model based trace variant analysis which is grounded in encoding the problem into SAT, and a family of heuristic alternatives including a very light sampling technique that represents a good trade-off between quality of the trace variants identified, and the complexity of the analysis. All the techniques of the paper are implemented in two open-source tools, and experiments with publicly available benchmarks are reported. Highlights: A novel approach to generalize the notion of trace variant of an event log. Proposal for two generalized trace variants: process and subnets, to cope with concurrency and loop behavior. An encoding of the problem into SAT. A sampling strategy to cope with the complexity of the problem, that incorporates certain statistical guarantees. A qualitative and quantitative evaluation over well-known benchmarks.