## 5 Trace Sampling Based on Type, Duration, and Errors
### Hybrid Approach Based on Types and Durations  
The hybrid approach takes into account both trace type and duration information. This algorithm performs accurate sampling if both durations and types are important. Assume that traces are already grouped into trace types. We generate the histogram of durations for each group and apply the procedure described in the previous subsection. We also consider the probability of a trace type. Common types will be sampled more aggressively. Let  
\[H^{(k)}=\{n_{1}^{(k)},\ldots,n_{m}^{(k)}\},\ k=1,\ldots,M, \tag{18}\]  
be the histogram of durations of the \(k\)-th trace type and \(n_{s}^{(k)}\) be the number of traces in the \(s\)-th bin of the \(k\)-th type. As above, \(M\) is the number of different types, and \(m\) is the number of bins in the histogram. Let \(N_{k}\) be the number of traces in the \(k\)-th trace type:  
\[N_{k}=\sum_{s=1}^{m}n_{s}^{(k)}. \tag{19}\]  
Let \(N\) be the total number of traces:  
\[N=\sum_{k=1}^{M}N_{k}. \tag{20}\]  
Let  
\[p^{(k)}=\{p_{1}^{(k)},\ldots,p_{m}^{(k)}\},\ p_{s}^{(k)}=\frac{n_{s}^{(k)}}{N_ {k}},\ k=1,\ldots,M, \tag{21}\]  
and  
\[P=\{p_{1},\ldots,p_{M}\},\ p_{k}=\frac{N_{k}}{N}. \tag{22}\]  
We denote the sampling rate of a trace from the \(s\)-th bin of the \(k\)-th trace type by \(r_{s}^{(k)}\). It shows the fraction of traces that should be stored. We compute it by the following formula as inversely proportional to the corresponding probabilities:  
\[r_{s}^{(k)}=1-(p_{k})^{\alpha}\Big{(}p_{s}^{(k)}\Big{)}^{\beta}, \tag{23}\]  
where \(\alpha,\beta\geq 0\) are some unknown parameters to be tuned to meet the requirement for the final sampling rate \(r\). Let us show how it could be carried out. Let \(N_{k}^{*}\) be the number of traces in the \(k\)-th trace type after sampling. Let \(n_{s}^{(k)*}\) be the number of traces in the \(s\)-th bin and the \(k\)-th trace type after sampling:  
\[N_{k}^{*}=\sum_{s=1}^{m}n_{s}^{(k)*}=\sum_{s=1}^{m}n_{s}^{(k)}r_{s}^{(k)}=N_{k} \sum_{s=1}^{m}p_{s}^{(k)}\bigg{(}1-(p_{k})^{a}\Big{(}p_{s}^{(k)}\Big{)}^{\beta} \bigg{)}. \tag{24}\]  
Let \(N^{*}\) be the total number of traces after sampling across all types and durations:  
\[N^{*}=\sum_{k=1}^{M}N_{k}^{*}=\sum_{k=1}^{M}N_{k}\sum_{s=1}^{m}p_{s}^{(k)} \bigg{(}1-(p_{k})^{a}\Big{(}p_{s}^{(k)}\Big{)}^{\beta}\bigg{)}=NG(\alpha,\beta), \tag{25}\]  
where  
\[r=\frac{N^{*}}{N}=G(\alpha,\beta)=\sum_{k=1}^{M}\sum_{s=1}^{m}p_{k}p_{s}^{(k) }\bigg{(}1-(p_{k})^{a}\Big{(}p_{s}^{(k)}\Big{)}^{\beta}\bigg{)} \tag{26}\]  
is the required final sampling rate that can be accomplished by appropriately selecting parameters \(\alpha\) and \(\beta\). First, we will illustrate this procedure when \(\alpha=\beta\). Figure 8 reveals the procedure for a specific trace type containing 3996 traces. The left figure shows the scatter plot of durations. The right figure shows the histogram of durations with 7 bins before and after the samplings. The value \(\beta=0.1\) corresponds to the sampling that stores 1104 traces. The next value \(\beta=0.05\) stores 599 traces. The value \(\beta=0.025\) corresponds to the sampling with 315 preserved traces. Finally, the value \(\beta=0.01\) stores 131 traces. The last one corresponds to the 3.3% sampling rate. In addition, the probability of this trace type is 0.2, which also impacts the sampling rates with \(\alpha=\beta\) setting. Figure 9 shows the hybrid procedure for another trace type with the probability 0.0048. It contains only 98 traces and is a rare type compared to the previous example. It also corresponds to the setting \(\alpha=\beta\). The right figure shows the sampling results for different values of \(\beta\). For example, the value \(\beta=0.01\) corresponds to the sampling that stores only 7 traces of this specific type. It corresponds to the 7.1% sampling rate. The value \(\beta=0.025\) corresponds to the 18.4% sampling rate. The value \(\beta=0.05\) stores 31 traces and corresponds to the 31.6% sampling rate. Finally, the value \(\beta=0.1\) corresponds to the sampling rate 52%.