## 5 Trace Sampling Based on Type, Duration, and Errors
### Sampling by Trace Type  
Assume that we know how to determine a trace type. Let \(M\) be the number of trace types for a specific period and \(N_{k},k=1,\ldots,M\) be the number of traces in each type. This information should be collected/updated for a recent period, as the number of trace types and the trace-flow velocity are subject to rapid changes in modern applications. Let \(N\) be the number of all traces before sampling:  
\[N=\sum_{k=1}^{M}N_{k}, \tag{1}\]  
and \(p_{k}(type)=N_{k}/N\), \(k=1,\ldots,M\) be the probability of the occurrence of the \(k\)-th type. Let \(r_{k}(type)\) and \(N_{k}^{*},k=1,\ldots,M\) be the sampling rate (the percentage/fraction of stored traces) and the number of traces after the sampling of the \(k\)-th type, respectively:  
\[N_{k}^{*}=r_{k}(type)N_{k},\ k=1,\ldots,M, \tag{2}\]  
where \(N_{k}^{*}\) should be rounded to the closest integer. Also, we denote by \(N^{*}\) the total number of all traces after the sampling  
\[N^{*}=\sum_{k=1}^{M}N_{k}^{*}. \tag{3}\]The ratio \(r=N^{*}/N\) is the final sampling rate. We propose to compute the sampling rate \(r_{k}\) as inversely proportional to the probability \(p_{k}(type)\):  
\[r_{k}(type)=1-(p_{k}(type))^{\alpha},\ \alpha>0, \tag{4}\]  
where \(\alpha\) is a parameter that a user should determine to satisfy the needed final sampling rate \(r\). Generally, the more frequent a trace type, the lower the corresponding sampling rate \(r_{k}\). Let us see how the parameter \(\alpha\) should be determined if the final user requirement is known:  
\[N^{*}=\sum_{k=1}^{M}N_{k}^{*}=\sum_{k=1}^{M}r_{k}N_{k}=\sum_{k=1}^{M}(1-(p_{k} )^{\alpha})N_{k}=N\sum_{k=1}^{M}p_{k}(1-(p_{k})^{\alpha})=NG_{type}(\alpha), \tag{5}\]  
where  
\[r=N^{*}/N=G_{type}(\alpha)=\sum_{k=1}^{M}p_{k}(type)(1-(p_{k}(type))^{\alpha}). \tag{6}\]  
This can be considered an analog of the Gini index, showing the total sampling rate. For a specific dataset of traces, we can compute the values of \(G(\alpha)\) across different \(\alpha\) and determine its value to satisfy a user's requirement. We can try to estimate the proper value of \(\alpha\) based on the recent collection of traces (say, for the last 2 h) and dynamically update those values to meet the requirement. Let us illustrate how this procedure works for a specific application. Figure 2 shows the distribution of traces across different trace types. There are types with almost 4000 traces and very rare ones, like ones with 3 representatives. Overall, we detected \(20,425\) traces distributed across 28 different trace types. Figure 3 and Table 1 reveal how different rates compress traces across types. We experimented with \(\alpha=1,0.5,0.25,\) and \(0.1\). The sampling rate is always smaller for common trace types and larger for rare ones (see Table 1). Smaller values of \(\alpha\) correspond to smaller final sampling rates. When \(\alpha=1\), we store \(17,903\) traces across all types: \(87.7\%\) of all traces. When \(\alpha=0.5\), we store \(13,629\) traces, \(66.7\%\) of all traces. For \(\alpha=0.25\), we store \(8882\) traces, \(43.5\%\). When \(\alpha=0.1\), we store \(4273\) traces, \(20.9\%\) of all traces. Let us inspect some of the sampling rates for specific types. The most frequent type contains 3996 traces with the probability \(p=0.2\). The corresponding sampling rate (for \(\alpha=1\)) is \(80.5\%\), and \(3215\) traces from this class were stored. One of the rarest types contains  
Figure 2: The distribution of traces across different types for a specific application. 3 traces with almost zero probability. The sampling rate is almost 100%, and we store two or three traces for different \(\alpha\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Type Index** & **Original Numbers** & \(\mathbf{\alpha=1}\) & \(\mathbf{\alpha=0.5}\) & \(\mathbf{\alpha=0.25}\) & \(\mathbf{\alpha=0.1}\) \\ \hline  
\hline Total & 20,425 & 17,903 & 13,629 & 8882 & 4273 \\ \hline Rate & - & 87.7\% & 66.7\% & 43.5\% & 20.9\% \\ \hline \hline \end{tabular}
\end{table}