## 5 Trace Sampling Based on Type, Duration, and Errors
### Sampling by a Trace Duration  
In this subsection, we consider the sampling of traces based on their durations. This setup is reasonable if we have a few trace types where traces have almost the same average durations. We would like to keep all traces with some average durations and those with extraordinarily short or long ones. Assume \(N\) traces with durations \(\{d_{k}\}_{k=1}^{N}\). Let \(D(m)\) be the corresponding histogram of durations with \(m\) number of bins:  
\[D(m)=\{n_{1},\ldots,n_{m}\}, \tag{7}\]  
where \(n_{s},s=1,\ldots,m-1\) is the number of traces with durations within intervals \([t_{s-1},t_{s})\), \(s=1,\ldots,m-1\) and \(n_{m}\) with durations within \([t_{m-1},t_{m}]\). Let \(p_{s}(dur)\), \(s=1,\ldots,m\) be the probability that a trace has a duration from the \(s\)-th bin:  
\[p_{s}(dur)=\frac{n_{s}}{N},s=1,\ldots,m. \tag{8}\]  
We determine the sampling rate \(r_{s}(dur)\) of a trace with a duration within the \(s\)-th bin to be inversely proportional to the corresponding probability \(p_{s}(dur)\):  
\[r_{s}(dur)=1-(p_{s}(dur))^{\beta},\ s=1,\ldots,m,\ \beta>0, \tag{9}\]  
where \(\beta\) is the parameter to meet a user's requirement. Let \(n_{s}^{*}\) be the number of traces after sampling in the \(s\)-th bin:  
\[n_{s}^{*}=r_{s}(dur)n_{s}. \tag{10}\]  
Let \(N^{*}\) be the total number of traces after the sampling:  
\[N^{*}=\sum_{s=1}^{m}n_{s}^{*}=\sum_{s=1}^{m}r_{s}(dur)n_{s}=N\sum_{s=1}^{m} \left(1-(p_{s})^{\beta}\right)p_{s}=NG_{dur}(\beta), \tag{11}\]  
Figure 4: The values of \(G_{type}(\alpha)\) show the final sampling rates for different \(\alpha\). The red-cross corresponds to \(\alpha=0.044\) with the final sampling rate \(r=0.099\) (around 10%). where  
\[r=N^{*}/N=G_{dur}(\beta)=\sum_{k=1}^{M}p_{k}(dur)\Big{(}1-(p_{k}(dur))^{\beta} \Big{)} \tag{12}\]  
is the total sampling rate for different values of parameter \(\beta\). Let us illustrate how this procedure works for the same dataset of traces presented earlier. We will skip the trace types and will look into the trace durations. Figure 5 shows the distribution of traces with durations in different time intervals. It shows three dominant time intervals in which the most traces are concentrated. We can aggressively sample those frequent traces and moderately sample the rare ones outside the dense areas. Table 2 shows how the sampling procedure works for different \(\beta\) parameter values (we use seven bins). The first column of Table 2, \"Time Intervals\", shows the seven intervals of duration. The intervals have equal lengths, although the bins could be nonuniform. The second column shows the initial number of traces with the durations within the corresponding time intervals. The remaining columns show the numbers after sampling with the corresponding \(\beta\). The last row of Table 2 reveals the final sampling rates. The bigger the value of \(\beta\), the more severe the reduction in traces. The value \(\beta=0.1\) provides a sampling rate of around 13%. Figure 6 visualizes the results of Table 2.  
If the requirement is to sample exactly 10% of traces, then Figure 7 shows the parameter \(\beta\) estimation based on the values of \(G_{dur}(\beta)\). The red cross indicates that \(\beta=0.083\) provides a sampling rate of 0.0996. \begin{table}
\begin{tabular}{l c c c c c} \hline
**Time Intervals** & **Original Numbers** & \(\beta=1\) & \(\beta=0.5\) & \(\beta=0.25\) & \(\beta=0.1\) \\ \hline \([9,1828)\) & 6685 & 4498 & 2861 & 1629 & 707 \\ \([1828,3647)\) & 5061 & 3808 & 2542 & 1491 & 660 \\ \([3647,5466)\) & 6328 & 4368 & 2806 & 1607 & 700 \\ \([5466,7284)\) & 81 & 81 & 76 & 61 & 35 \\ \([7284,9103)\) & 235 & 233 & 210 & 159 & 85 \\ \([9103,10922)\) & 1111 & 1051 & 852 & 575 & 281 \\ \([10922,12741]\) & 925 & 884 & 729 & 499 & 247 \\ \hline Total & 20,425 & 14,923 & 10,076 & 6021 & 2715 \\ \hline Rate & - & 73.1\% & 49.3\% & 29.5\% & 13.3\% \\ \hline \end{tabular}
\end{table} 
Table 2: The number of traces before and after the sampling. Figure 5: The distribution of traces with different durations (in milliseconds).