# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 2 Related Work
### Incremental Pattern Discovery  
Data mining is used to find implicit but meaningful knowledge appearing in databases, and it is commonly used in several domains such as market basket analytics, recommendation systems, behavior analysis and prediction systems. The fundamental way to mine relationships between items is called association-rule mining [1; 2]. The first algorithm for this task is Apriori [1]. It finds the set of frequent itemsets (FIs) based on a minimum support threshold, and then generates a set of association rules (ARs) in a second stage according to a minimum confidence threshold. Apriori performs a level-wise search. Thus, it can produce numerous candidates at each level to find the actual FIs. To speed up the mining process, [PERSON] et al. [2] designed the frequent-pattern (FP)-growth algorithm and developed the FP-tree structure. FP-growth recursively mines the set of FIs without generating candidates. Several algorithms were developed to discover ARs or FIs and it is an active research area [4; 5; 6; 7].  
In real-life situations, the size of the database may change over time. For example, some transactions may be inserted into a database and some transactions may be removed. To handle this case, the discovered information should be updated. However, traditional algorithms operate in batch mode. Thus, they must be applied again to mine the updated database without reusing results from its previous execution, even if only very few minor updates are performed. To handle this situation for dynamic databases, [PERSON] et al. designed the FUP (Fast UPdated) concept [25] to maintain information about the discovered frequent itemsets for incremental data mining. It categorizes itemsets based on four cases. Then, the itemsets of each case are updated and maintained by a specific updating procedure. The four FUP cases are illustrated in Figure 1.  
In Case 1, an itemset remains a large (frequent) itemset after a database update. Thus, this itemset does not influence the final rules. For itemsets in Case 2, rules are updated since information about the inserted transactions is kept for maintenance. In this case, some rules may become invalid since, when the database is updated, the frequency of each itemset may become smaller than the updated minimum support threshold (count).  
In Case 4, an itemset remains small (infrequent) after the database update. Thus, it does not affect the final result and itemsets in this case can be ignored. In Case 3, an itemset was not kept when mining the original database. Hence, the original database needs to be re-scanned to obtain the itemset support value for maintenance. In this case, some rules may arise after the database update.  
Since the FUP concept applies an Apriori-like approach, which may be inefficient, [PERSON] et al. developed the FUFP-tree (Fast Updated Frequent Pattern tree) algorithm to update frequent itemsets for transaction insertion [26]. It uses an FP-tree-like structure to store information about frequent itemsets in a compressed tree. An FP-growth like approach is applied to discover the updated information without candidate generation. Many extensions of the FUP concept were designed to handle dynamic databases with transaction insertion [27].