# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 2 Related Work
### High Average-Utility Itemset Mining  
Traditional algorithms for FIM/ARM only consider the frequency of items in binary databases to mine patterns. Other factors such as the importance, interest and weight of items are not considered. Thus, the provided information may be insufficient for a manager/retailer and wrong decisions may be taken based on these patterns. HUIM (High-Utility Itemset Mining) [8; 9; 13; 14; 15] was designed to take into account purchase quantities (internal utility) and unit profits (external utility) of items to reveal profitable itemsets. An itemset is said to be a HUI (High-Utility Itemset) if its utility value is larger than the minimum high-utility threshold (count). To avoid the \"combinational exploration\" problem and ensure that there is a downward closure property, the HTWUI (High Transaction-Weighted Utilization Itemset) concept was presented, and a property called the TWDC (Transaction-Weighted Downward Closure) property [10] for mining HUIs. Based on the concept of HTWUI, correct and complete algorithms were designed to discover HUIs. [PERSON] et al. designed the HUP-tree (High Utility Pattern tree) algorithm [11] to efficiently discover the set of HUIs based on the developed HUP-tree structure. It keeps only the 1-HTWUIs to explore the search space of itemsets and do not generate candidates. The HUP-tree algorithm is much more efficient than traditional Apriori-like approaches. The UP-Growth+ algorithm and the UP-tree structure were designed by [PERSON] et al. [28]. They adopt several pruning strategies to reduce the number of unpromising candidates for mining the actual HUIs. [PERSON] et al. [12], respectively, developed the UL-structure (Utility-List) and the HUI-Miner algorithm to efficiently find the set of HUIs. HUI-Miner generate candidates but can still reveal the complete set of HUIs. In addition, it uses a simple join operation to generate \(k\)-itemsets based on the UL structure and the enumeration tree without candidate generation. Several approaches for HUIM have been developed and it is an active research area [16; 17; 18; 19]. Figure 1: The four cases of the FUP concept. In HUIM, the utility of an itemset is the sum of the utilities of its items. This ignores the length of the itemset and that the utility of an itemset often increases with its size. It also sometimes provides redundant information. For example, any combination of items with caviar may be considered as a HUI. This is an unfair way of assessing whether an itemset is a HUI using a single minimum high-utility threshold (count). High average-utility itemset mining (HAUIM) [20] provides a measure to assess the average-utility of an itemset based on its length. The average-utility of an itemset is its total utility divided by the number of items that it contains. The first Apriori-like algorithm for HAUIM is called TPAU [20]. It generates candidates at each level that it then evaluates. The TPAU algorithm overestimates the average-utility of itemsets using the (_auub_) upper-bound model to obtain a downward closure property, which is used to ensure the completeness and correctness for mining HAUIs (High Average-Utility Itemsets). [PERSON] et al. designed the HAUP-tree (High Average-Utility Pattern tree) [21] to keep information for mining patterns, thus speeding up their discovery. The quantities of prefix items of the current processed item are then kept as an array and attached to the processed item (node). An efficient HAUI-Miner algorithm [22] was also presented, which uses a link-list structure to store information for mining patterns. The HAUI-Miner algorithm is the state-of-the-art algorithm based on the _auub_ model to mine HAUIs. An IHAUPM algorithm [29] was presented to incrementally update the discovered HAUIs. It is the state-of-the-art algorithm for incremental maintenance of high average-utility itemsets for transaction insertion.