# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 4 Proposed TKAUS Algorithm
### Proposed TKAUS Algorithm
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multicolumn{2}{c}{**Time**} & \multicolumn{2}{c}{**Max Memory**} & \multicolumn{2}{c}{**Candidates**} \\  & **Top-\(k\)EHAUSM** & **TKAUS** & **Top-\(k\)EHAUSM** & **TKAUS** & **Top-\(k\)EHAUSM** & **TKAUS** \\ \hline \hline Bible k = 200 & 1621.854 & 22.548 & 410.481 & 323.106 & 15,724 & 6143 \\ \hline Leviathan k = 500 & 1490.095 & 16.152 & 351.635 & 319.743 & 73,712 & 40,918 \\ \hline Sign k = 500 & 3420.941 & 79.63 & 353.422 & 312.315 & 649,694,319 & 990,105 \\ \hline Yoochoose k = 8000 & 13,127.643 & 2429.662 & 777.194 & 397.227 & 29,703,530,233 & 37,185,721 \\ \hline Kosarak\_10K k = 9 & 1.79 & 1.251 & 102.335 & 39.050 & 54 & 348 \\ \hline SynDataset\_80K k = 200 & 1172.576 & 65.639 & 480.374 & 373.288 & 2574 & 5630 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Effectiveness of Top-\(k\)EHAUSM and TKAUS. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multicolumn{2}{c}{**Time**} & \multicolumn{2}{c}{**Max Memory**} & \multicolumn{2}{c}{**Candidates**} \\  & **TKAUS** & **TKUS** & **TKAUS** & **TKUS** & **TKAUS** & **TKUS** \\ \hline Bible k = 200 & 22.548 & 888 & 323.106 & 4247 & 6143 & 17,059 \\ Leviathan k = 500 & 16.152 & 339 & 319.743 & 2893 & 40,918 & 40,918 \\ \hline Sign k = 500 & 79.63 & 193 & 312.315 & 2682 & 990,105 & 193,477 \\ Yoochoose k = 8000 & 2429.662 & 35 & 397.227 & 2780 & 37,185,721 & 180,641 \\ \hline Kosarak\_10K k = 9 & 1.251 & 13 & 39.050 & 2279 & 348 & 2001 \\ \hline SynDataset\_80K k = 200 & 65.639 & 839 & 373.288 & 5483 & 5630 & 972,569 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Effectiveness of TKAUS and TKUS. ### Number of Candidates

The number of candidates could be regarded as a crucial measure of the search space. The larger dataset generates more candidates from a macro perspective. In fact, TKUS and TKAUS generate fewer candidates than other early algorithms by adopting the projection mechanism. [PERSON] et al. in [48] defined search space shrinkage rate (SSSR) for evaluation and validated that TKUS generates fewer candidates than TKHUS-Span in the experiment. Moreover, among the different datasets, the longer the average length of the sequence is, the greater the number of candidates is. The algorithms also generate more candidates as the number of sequences increases. With increasing parameter \(k\), the threshold for mining decreases, and the quantity of candidates increases. The upper bound proposed in EHAUSM overestimates the candidate sequence utility based on the maximum item utility in the _remaining sequence_ or the utility of the whole sequence so that it is a larger value far beyond the actual utility of the candidate sequence. Finally, more candidates were generated by the \"_extension_\" operation. But in Figure 3e, the number of candidates in top-\(k\) EHAUSM is indeed less than in TKAUS. If the sequences in the database vary considerably in length, and most of the item is interesting to the user and has a high utility value, the TKAUS may lose its advantages. Figure 2: Runtime for various \(k\) in different dataset. The main objective of TKUS is to find top-\(k\) HUSPs, but the purpose of the proposed TKAUS is to identify top-\(k\) HAUSPs. The average utility of pattern not only depends on its utility but also involves its length. Then, patterns with low utility also have great potential to be high average-utility ones, which have a corresponding short length, and in Figure 3, it is reasonable that the number of candidates generated in TKAUS is less than in TKUS, especially in Figure 3f. Compared with the feature of the dataset, this could be a reason that the value of item utility in the dataset is relatively concentrated, i.e., the utility of item is the same level, and the length of pattern has a great effect on the sum of utility than the average utility of items in a pattern.