## 4 Materials and Methods
### Efficient Construction of Behavior Graphs
It is important to note, however, that for all values of \(p\) our new algorithm runs is significantly more efficient than the baseline algorithm: with \(p=0\), the new algorithm takes 0.47% of the time needed by the naive construction, while for \(p=1\) this figure grows to 4.39%. An additional experiment is illustrated to provide an answer to \(Q4\). As with the first experiment, we increase the number of traces \(n\) in the uncertain log, while keeping the other parameters fixed: \(l=10\) and \(p=0.5\). We then perform the behavior graph construction with both methods, and we measure the memory consumption derived from the transitive reduction method (keeping in memory one behavior graph for each uncertain trace) versus the improved method (which generates a multiset of behavior graphs, one for each variant in the uncertain log). The results are summarized in Table 4.1 Please note that when \(n\) increases, more and more uncertain traces are characterized by the same behavior graph, and can then be grouped in the same variant. This allows the improved algorithm to store the uncertain log more effectively. At \(n=15\),000, the space needed by the multiset of behavior graphs is 59.2%, a sizable improvement in memory requirements when analyzing uncertain event logs of substantial dimensions. This improvement in memory consumption is a consequence of the new technique used in this paper to obtain the timestamp list, which enables such refinement with respect to the technique illustrated in [5]. Table 4.2 Time in seconds for the creation of the behavior graphs for synthetic logs with \(n=100\) traces and \(p=0.5\) of uncertain events, with increasing trace length \(l\). Finally, to elucidate research question \(Q5\) we compared the computation time for behavior graphs creation on real-life event logs, where we artificially inserted timestamp uncertainty in progressively higher percentage of uncertain events \(p\) as described for the experiments above. We considered three event logs: an event log tracking the activities of the help desk process of an Italian software company,

Table 4.3 Memory consumption in bytes needed to store the behavior graphs for synthetic uncertain event logs with traces of length \(l=10\) events and timestamp uncertainty of \(p=0.5\), with an increasing number of traces \(n\). Table 4.4 Time in seconds for the creation of the behavior graphs for synthetic logs with \(n=100\) traces of length \(l=100\) events, with increasing percentages of timestamp uncertainty \(p\). a log related to the management of road traffic fines in an Italian municipality, and a log from the BPI Challenge 2012 related to a loan application process. The results, presented in Figure 15, closely adhere to the findings of the experiments with synthetically generated uncertain event data: the novel method provides a substantial speedup that remains rather stable with respect to the percentage \(p\) of uncertain events added in the log. ### Applications of the Behavior Graph Construction

In Section 1 we saw how building the behavior graph is a fundamental preprocessing step for both process discovery and conformance checking when dealing with uncertain event logs. In the previous section, we showed in practice how the novel algorithm presented in this paper impacts the computation time for the construction of behavior graphs. Now, let us have a glance into the effect of the speedup when applied to process mining techniques. In this additional experiment we consider the conformance checking problem. In [2] we proposed an approach to compute upper and lower bounds for the conformance score of a trace against a reference Petri net through the alignment technique, which yields alignments for the best- and worst-case scenarios of an uncertain trace as illustrated in Section 1. The experiment is set up to assess the effect of the new behavior graph construction on the overall performance of conformance checking over uncertain data.