# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 4 Proposed TKAUS Algorithm
### Proposed TKAUS Algorithm
Its memory complexity is \(\mathcal{O}(|D||Q|)+\mathcal{O}(|D||Q|)+\mathcal{O}(|D||Q|)+\mathcal{O}(|I|)+ \mathcal{O}(|I|)\), which equals \(\mathcal{O}(|D||Q|+|I|)\). As for the _update_ function, the generated sequence is inserted into \(T\)\(K\)\(L\)\(ist\), and the sequence with the lowest average utility is deleted. Its time complexity of the process is \(\mathcal{O}(k\log k)\). In addition, the memory complexity of the update function is \(\mathcal{O}(\log k)\). Suppose \(L\) is the sequence length of the longest generated one in the above process. Then, \(|Q|\leqslant L\). Therefore, the maximum number of recursive calls is \(|I|^{L}\) in the function _projection_-TKAUS. According to the above, the time complexity and memory complexity of TKAUS are \(\mathcal{O}(|D||Q|+|I|\log|I|)+|I|^{L}\times\mathcal{O}(|D||Q|)+|I|^{L}\times |I|\times\mathcal{O}(k\log k)\) and \(\mathcal{O}(|D||Q|+\log|I|)+L\times\mathcal{O}(|D||Q|+|I|)+L\times|I|\times \mathcal{O}(logk)\), respectively. In the worst case where \(|Q|=L\), the time complexity and memory complexity are \(\mathcal{O}(|I|^{L}|D|+|I|\log|I|+|I|^{L}+1)k\log k)\) and \(\mathcal{O}(L^{2}|D|+\log|I|+L|I|+L|I|\log k)\). ## 5 Experiments

In this section, we conducted experiments to compare and contrast the performance of the proposed TKAUS algorithm. The algorithms are implemented in Java and developed in Eclipse IDE, and the experiments are conducted on a cloud virtual machine equipped with an Intel(R) Xeon(R) Platinum 8255c CPU and Linux version 3.10.0-1160.31.1.e17.x86_64 operating system. ### Experimental Settings

To evaluate performance, the experiments are conducted on seven datasets with different characteristics, which are obtained from SPMF ([[http://www.philippe-fournier-viger.com/spmf/](http://www.philippe-fournier-viger.com/spmf/)]([http://www.philippe-fournier-viger.com/spmf/](http://www.philippe-fournier-viger.com/spmf/))), accessed on 20 December 2022. Currently, there is a scarcity of existing works focusing on top-\(k\) HAUSPM. For the performance tests, we assess the execution time, space overhead, the total number of candidates generated, and scalability toward large datasets by comparing with the TKUS algorithm [48]. The details of the experiments are given as follows. The Bible is a conversion dataset from part of the Bible, and each word is considered to be an item. Each sentence is considered to be a sequence, and the lengths of sequences are mainly medium in the Bible. The Leviathan is also a conversion dataset from the novel Leviathan by [PERSON] (1651). It is similar to the previous one. The special word in the novel was replaced by the digital item. The Sign is a new format of the sign language utterance dataset, and the original one was created by the National Center for Sign Language and Gesture Resources at Boston University. There are approximately 730 sequences, and most of them are long. The Kosarak is a clickstream dataset from a Hungarian online news portal. It is difficult to deal with the extremely high sequence length in this dataset. Yoochoose is also clickstream data from e-commerce in a new format. It is composed of a single-itemset or multi-itemset sequence and has been used in Ref. [48]. For all datasets, five parameters are used for the feature description. \(|D|\) indicates the number of \(q\)-sequences in dataset. \(|I|\) indicates the number of distinct items in a dataset. \(AvgLen\) and \(MaxLen\) are the average length and the maximal length of \(q\)-sequence in dataset, respectively. The average number of \(q\)-itemsets in one \(q\)-sequence is denoted as \(AvgSeqSize\). The average number of \(q\)-items in one \(q\)-itemset is denoted as \(AvgSetSize\). The details of datasets are given in Table 3.

### Strategy Performance and Effectiveness Analysis

In this subsection, the experimental results will be used to assess the algorithm's performance. The top-\(k\) EHAUSM was selected as a comparison based on EHAUSM, which is the first approach for HAUSPM in general case [35].