# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 4 Proposed TKAUS Algorithm
### Data Structure and Projection Strategies  
In the framework of the proposed algorithm, the mining process first scans the given \(q\)-sequence database once. The lexicographic sequence tree as the complete search space has been used in SPM and HUSPM [38]. Then, [PERSON] [19] presented the lexicographic quantitative sequence tree (LQS-tree) structure. Each node of this LQS-tree structure is associated with a candidate, which consists of the \(q\)-sequence and its utility. The root of this tree is null. All child nodes are arranged in ascending order, for instance, alphabetical order. The child node is a prefix-based extension of its parent node. There are two kinds of _extension positions_ for the appending item in a sequence. One is the end of the last itemset. The other position is after the last itemset as a new itemset. Both \(I\)-Extension and \(S\)-Extension are operations of \({}^{\prime}\)_extension_\({}^{\prime}\) to generate new sequences. For example, consider a \(l\)-sequence \(s\) and an appending item \(i\), the size of \(s\) is \(k\), \(I\)-Extension of sequence is to append item \(i\) to the end of last itemset in sequence \(s\), notated as \(s\oplus i\), the new generate sequence is \((l+1)\)-sequence \(s^{\prime}\), the length of \(s^{\prime}\) is \((l+1)\) and the size of \(s^{\prime}\) still is \(k\). \(S\)-Extension of sequence is to let itemset \(i\) as a new one \(\{i\}\) and append to the end of sequence \(s\), notated as \(s\otimes i\). In this way, the newly generated sequence also is \((l+1)\)-sequence \(s^{\prime}\) which is \((l+1)\) in length, but the size of \(s^{\prime}\) is \((k+1)\). In some cases, the _instances_ of the sequence \(S\) may appear more than one position, and the set of positions of _instances_ is denoted as \(P\colon\{p_{1},p_{2},\cdots,p_{w}\}\). [PERSON] et al. [48]presented the position of the last itemset in _instance_ is _extension position_. In \(q\)-sequence \(Q\), the sequence utility of \(S\) is the maximum utility of all _instances_. The last item within _instance_ is the _extension item_. The _remaining sequence_ is a subsequence from the item after the _extension item_ to the end of \(Q\), which is denoted as \(rs(S,p,Q)\). [PERSON] et al. defined the _remaining utility_ of \(S\) at the _extension position_\(p\) in \(Q\) as \(u_{rs}(S,p,Q)\)[20]. \[u_{rs}(S,p,Q)=\sum_{i^{\prime}\in Q\setminus i^{\prime}>S}u(i^{\prime})\]  
where \(i^{\prime}\succ S\) indicates that the position of item \(i^{\prime}\) is after the _extension position_\(p\). For instance, from Tables 1 and 2, the sequence \(\langle\{f\},\{g\}\rangle\) has _instances_ at position \(\langle 1,3\rangle\), \(\langle 2,3\rangle\) and \(\langle 1,2\rangle\) in \(Q_{5}\).The _extension position_ of these _instances_ are \(\langle 3\rangle\) and \(\langle 2\rangle\), and the item \(g\) is the _extension item_. Thus, the _remaining utility_ of \(\langle\{f\},\{g\}\rangle\) at _extension position_\(\langle 3\rangle\) in \(Q_{5}\) is \(u_{rs}(\langle f,g\rangle,\langle 3\rangle,Q_{5})=0\), and at _extension position_\(\langle 2\rangle\) is \(u_{rs}(\langle f,g\rangle,\langle 2\rangle,Q_{5})=17\). To calculate all the multiple _instances_ in a \(q\)-sequence is time-consuming. In [46; 48], the projected database was utilized to keep the necessary information in sequence. By adopting the utility-chain structure, these studies reduce calculation costs. The projected database of a sequence is composed of an information table and a utility chain. The utility chain in the structure consists of two parts: a head table and a utility list. The utility-chain structure gives the auxiliary information to facilitate pruning search space in HUS-Span [46]. In this work, the prefix extension average utility (abbreviated as PEAU) of the sequence is stored in the information table as a key piece. In addition to the maximum utility of all _instances_ and the utility of _remaining sequence_, the utility list also contains the length of _instance_ and _remaining sequence_.