# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 1 Introduction  
Mining useful or meaningful information is a major KDD (Knowledge Discovery in Database) task, which has been widely considered as interesting and useful for more than two decades. Association rulemining (ARM) is a basic KDD problem, designed to reveal correlations between purchased items in customer transactional records. A fundamental algorithm named Apriori [1] was first designed to mine association rules (ARs). It discovers patterns in a level-wise way in a static database. Initially, it finds the set of frequent itemsets based on a parameter called the minimum support threshold. Then, Apriori derives the set of ARs from these itemsets according to a second parameter called the minimum confidence threshold. Although this approach can find all the desired patterns, it can have very long runtimes and huge memory requirements. Based on this observation, the Frequent Pattern (FP)-growth [2] algorithm was proposed. It speeds up ARM by keeping information required for mining ARs in a compressed FP-tree structure. The FP-tree structure stores frequent items, which are later used for mining patterns in a recursive way, growing patterns from small patterns to longer patterns, without generating candidate patterns and using a depth-first search. [PERSON] et al. [3] then introduced a new vertical data structure called N-list, which keeps the required information for mining patterns, and an efficient PrePost algorithm to mine the set of frequent patterns. Several algorithms used in different domains and applications [4; 5; 6; 7] were developed to efficiently find different types of itemsets, respectively. Most approaches for ARM can only be applied on binary databases. Thus, it is considered that all items are equally interesting or important. The internal values (such as the purchase quantities of items) or the external values (such as the unit profits of items) are not taken into account in ARM. For this reason, ARM is unable to specifically reveal the profitable itemsets. Consequently, retailers or managers cannot take efficient decisions or choose appropriate sales strategies on the basis of the most profitable sets of products. For example, caviar may yield much more profit than bottles of milks in a supermarket. To solve this problem, HUIM (High-utility itemset mining) [8; 9] was introduced to discover the set of high-utility itemsets (HUIs). To reduce the search space and maintain the downward closure property, a transaction-weighted utility (TWU) model [10] was developed to find a set of patterns called HTWUIs (High Transaction-Weighted Utilization Itemsets). Discovering HTWUIs can be used to avoid the \"combinatorial explosion\" problem by maintaining the downward closure property for mining HUIs (High-utility Itemsets). [PERSON] et al. then presented a high-utility pattern (HUP)-tree [11] that keeps only 1-HTWUIs into a condense tree structure based on the TWU model. [PERSON] et al. [12] then developed the HUI-Miner algorithm and presented a utility-list (UL) structure for mining HUIs, which is the most efficient structure to mine HUIs. [PERSON] et al. then presented several works to address the problem of HUIM focusing on the on-shelf problem [13; 14]. [PERSON] then presented a top-\(k\) algorithm to efficiently find the top-\(k\) HUIs from the set of the discovered HUIs in the stream dataset [15]. Several algorithms [16; 17; 18; 19] were presented for specific applications and designed to mine various types of HUIs. Although HUIM can identify the set of profitable itemsets for decision-making, the utility of an itemset often increases when its size is increased. For example, any combination of caviar with another item may be considered as a high-utility itemset (HUI) for market basket analytics, which may mislead a manager/retailer and result in taking wrong or risky decisions. An alternative designed by [PERSON] et al. [20] is HAUIM (High Average-Utility Itemset Mining) to discover the set of HAUIs (High Average-Utility Itemsets) in databases.