## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
We first generate a Petri net with \(t\) transitions, simulate a log by playing out \(n=500\) traces, and add timestamp uncertainty with \(p=0.1\). We then compute the lower bound for conformance between the uncertain event log and the Petri net used as a source, and compare the overall execution time for conformance using the two different methods for the creation of the behavior graph. In this specific experiment, we also considered the other types of uncertainty in process mining illustrated in the taxonomy of [2], as well as all types of uncertainty simulate on the same log. The results are shown in Table 4.5 We can see that on very small nets (\(t=5\)), the alignment algorithm takes a short time to execute, so the speedup provided by the improved behavior graph construction has a larger impact on the total computation time (taking as little as 30.71% of the time to calculate alignments). With the increase of \(t\), the computation time for conformance checking using the fast construction of the behavior graph appears to stabilize around 65% of the time needed if we employ

Table 4.6 Execution times in seconds for real-life event logs with increasing percentages \(p\) of timestamp uncertainty. the naive construction when considering only one type of uncertainty in isolation. This translates in a reduction of roughly 35% of computation time for the very common problem of calculating the conformance score between event data and a reference model, a significant impact on performances of concrete applications of process mining over uncertain data. When compounding all types of uncertainty we see a similar effect, although for \(t=5\) the improved method takes 52.22% of the time required by the baseline construction, a less dramatic effect than the other uncertainty settings. This is because even at such small scales, the high number of realizations of traces slow down the alignment phase in the computation. In evaluating this result, it is important to consider that alignments are a notoriously time-intensive technique [20], since the technique is based on an A\({}^{*}\) search on a state space that consists of pairs of the activities in the trace combined with the possible actions in the model. As a consequence, the impact of the algorithm presented in this paper is limited by the characteristics of the implementation of such alignment technique; combining it with more refined alignment algorithms would further improve the gain in speed. In summary, the outcomes of the experiments show how our new algorithm hereby presented outperforms the previous method for creating the behavior graph on all the parameters in which the problem instance can scale in dimensions, in both the time and space dimensions. The experiment designed to answer \(Q3\) shows that like the naive algorithm, our novel method being is essentially insensitive to the percentage of events with uncertain timestamps contained in a trace. This fact is also verified by the experiment associated with \(Q5\) on real-life data with added time uncertainty. While for

Table 4.7 Relative variation in computation time obtained through the improved behavior graph construction when applied to the computation of conformance bounds between a synthetic uncertain log and a Petri net with an increasing number of transitions. The synthetic uncertain logs have \(n=500\) traces and timestamp uncertainty has been introduced with \(p=0.1\). every combination of parameters we benchmarked the novel algorithm runs in a fraction of time required by the baseline method, the experiments also confirm the improvements in asymptotic time complexity demonstrated through theoretical complexity analysis. ## 7 Related Work

The topic of process mining analysis over uncertain event data is relatively new, and little research has been carried out.