# Mining Top-\(k\) High Average-Utility Sequential Patterns for Resource Transformation
## 2 Related Work
### High Average-Utility Pattern Mining  
The calculation of average utility in HAUIM algorithms takes into account the length of pattern. This approach helps to identify short patterns that may be missed by traditional algorithms. Two-phase average-utility (TPAU) mining [26; 49] is the first HAUI mining algorithm. The average utility value does not satisfy the downward closure property. To address this limitation, TPAU proposed an average-utility upper bound auub, which maintains the property, because the value of auub is always larger than the average utility of pattern. The auub is utilized to improve mining performance by pruning. However, TPAU is bound by repeated scanning of the original database and generating a huge amount of candidate patterns. HAUI-Growth [50] was designed to limit the generation of candidates and to overcome multiple scanning. The average utility of each itemset was maintained as an array in the node of a HAUI-tree structure. Another approach, PBAU, proposed by [PERSON] et al. [28], is the projection-based mining algorithm, which uses index tables to reveal HAUIs. They used a tree structure to reduce the number of scans in the original database [27]. An enumeration tree structure was used in the algorithm HAUI-Tree [51]. However, the number of candidates generated by these tree-based methods is still high. With the list structure, MHAI [52] and HAUI-Miner [53] adopted the transaction-maximum utility and the maximum average utility as the utility upper bound to prune unpromising patterns, respectively. EHAUPM [54] proposed a revised tighter upper bound model (rtub) and looser upper bound (lub) and presented MAU-list based on a list structure. In the transaction database, to reduce the unpromising patterns, TUBHAUPM [55] proposed maximum following utility upper bound (mfuub), transaction-rival tight upper bound (trtub), and top-\(k\) revised transaction-maximum utility upper bound (krtmuub). By considering both vertical information of other transactions and horizontal information in the same transaction, VMHAUI [56] suggested three upper bounds by introducing vertical approaches [57]. By employing tighter upper bounds, the algorithm can hugely reduce the search space. Considering the protection of sensitive content, [PERSON] et al. designed an algorithm H-FHAUI [58] with a novel vertical utility list structure, TIU-VIU, for updating upper bounds quickly. [PERSON] et al. [59] employed the maximum remaining average-utility upper bound and tight maximum average-utility upper bound and proposed a HAUPM approach with the list-based structure. It is a limitation of HUSPM that the utility function tends to be biased toward discovering longer patterns. Based on the pattern-growth approach, [PERSON] et al. [34] proposed an approach to reveal the effect of pattern length in a web traversal sequence. The proposed average transaction-weighted utility (atwu) used the high average-utility concept, which was introduced in Ref. [31]. The search space was divided by the transaction-weighted utility (TWU) of each pattern, and the number of candidates was reduced. However, each item can occur more than once in most cases. This approach proposed by [PERSON] et al. was inapplicable to the general case [35]. [PERSON] et al. [35] proposed anti-monotonic upper bound (AMUB), bi-directional upper bound (BiUB), and four pruning strategies in algorithm EHAUSM. Three weak upper bounds, tweaub, rmwub, and tmwub, were proposed to prune all proper extensions of a sequence early. Moreover, [PERSON] et al. [60] considered the size of a sequence and proposed a framework of SPM for finding potential HAUSPs from the uncertain dataset. [PERSON] et al. proposed HAOP-Miner [61] and HANP-Miner [62] to discover the sequential pattern under the one-off condition and nonoverlapping sequential pattern. The reverse filling (Rf) algorithm was designed to avoid creating redundant nodes and to calculate the support effectively.