# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 4 Proposed TKAUS Algorithm
### Proposed TKAUS Algorithm
From lines 4 to 25, for each extended sequence, if the RSAU value is not less than the threshold, the extended sequence could be a top-\(k\) HAUSP or its prefix. After that \"_extension_\" operation, we compare all generated sequences in seqlist to the new minimum average-utility threshold according to their PEAU values. Then, the _projection_-TKAUS algorithm is called recursively. Algorithm 3 is \(\mathit{update}(S^{\prime},\mathit{minau},\mathit{TKList})\) algorithm. The lowest average-utility sequence is removed from \(\mathit{TKList}\) when the size exceeds the specified parameter. Meanwhile, the \(\mathit{minau}\) is updated to the sequence average utility of \(k\)th HAUSP in \(\mathit{TKList}\). ```
0: A generated sequence from \(S\), \(S^{\prime}\). The number of desired HAUSPs, \(k\). 0: A minimum average-utility threshold, \(minau\). A set of top-\(k\) high average-utility sequential patterns, \(T\)\(K\)\(L\)\(ist\). 1: scanning \(T\)\(K\)\(L\)\(ist\) once to:
2: (1) sorting all sequences by the sequence average utility in descending order, then getting the sequence with the lowest average-utility value \(lowest.au.seq\)
3: (2) getting the number of sequential patterns in \(T\)\(K\)\(List\), \(k^{\prime}\)
4:if\(k^{\prime}\geq k\)
5: Inserting \(S^{\prime}\) into \(T\)\(K\)\(L\)\(ist\)
6:\(minau\) = the average utility of \(k^{th}\) HAUSP in \(T\)\(K\)\(L\)\(ist\)
7: Removing \(lowest.au.seq\) from \(T\)\(K\)\(ist\)
8:else
9: Inserting \(S^{\prime}\) into \(T\)\(K\)\(L\)\(ist\)
10:endif
11:return\(minau\),\(T\)\(K\)\(L\)\(ist\)
```

**Algorithm 3**\(update(S^{\prime},minau,T\)\(K\)\(List)\) algorithm

### Complexity Analysis of the Proposed TKAUS Algorithm

Suppose the number of quantitative sequences in a quantitative sequential database is \(|D|\), \(|Q|\) is the average number of items of the quantitative sequence in the database, and \(|I|\) is the number of distinct items in the database. \(k\) represents the desired number of HAUSPs. It is a user-specified parameter. Therefore, in the first scan of the original database, \(\mathcal{O}(|D|\times|Q|)\)\(q\)-items are processed to calculate the information of each one. This information is stored in a projected database, and \(\mathcal{O}(|D|\times|Q|)\) is also the memory complexity of the first scan. Then, in TKAUS, the \(k^{th}\) highest average-utility value of all 1-sequences is set as the initial threshold, so it takes \(\mathcal{O}(|I|\log|I|)\) in order to sort all 1-sequences in an average utility descending order using the quick sorting algorithm. In the sorting step, the memory complexity is \(\mathcal{O}(\log|I|)\). TKAUS next updates \(T\)\(K\)\(L\)\(ist\), which is used to store HAUSPs. At this time, in the worst case, it takes \(\mathcal{O}(|D|\times|Q|)\) to calculate the actual sequence average utility for each sequence. Meanwhile, TKAUS calls the recursive function _projection_-TKAUS. The required processing for comparing the threshold and the PEAU of each sequence is \(\mathcal{O}(|D|\times|Q|)\). In _projection_-TKAUS, the \((k+1)\)-sequence is generated from the \(k\)-sequence by appending each item. In addition, two conditional lists are constructed to store the appending items. It takes \(\mathcal{O}(|D|\times|Q|)\) to scan the projected database and to mark the unpromising items with low RSAU. Then, the unpromising items will be deleted from the lists. The largest size of a conditional list is \(|I|\). The algorithm next traverses the reduced lists and appends each item to the prefix. Meanwhile, TKAUS finds the HAUSPs and calls the _update_ function. The required amount of processing to calculate the actual sequence average utility is \(\mathcal{O}(|D|\times|Q|)\). The generated sequence with high PEAU is set as a new prefix and is inserted in the projected database. Repeat the above process for all the prefixes. The corresponding time complexity is \(\mathcal{O}(|D||Q|)+\mathcal{O}(|D||Q|)+\mathcal{O}(|D||Q|)\), which equals \(\mathcal{O}(|D||Q|)\).