# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 4 Proposed FUP-HAUIM Algorithm with Transaction Insertion
### The Adapted Fast Updated Concept
Thus, the proposed FUP-HAUIMI algorithm may need to check more patterns in the enumeration tree to check if the supersets must be generated. However, in general cases, the FUP-HAUIMI algorithm still checks less patterns than other algorithms. This shows that the AUL-structures and the adapted FUP concept can successfully reduce the cost of incremental mining of average-utility itemsets. Results for various DR values and a fixed TH are shown in Figure 6.0

Again, we can observe that the FUP-HAUIMI algorithm needs to examine more candidates in very sparse and dense datasets such as the datasets of Figure 10c,d. However, for the other datasets such as the datasets of Figure 10a,b,e, the proposed FUP-HAUIMI algorithm outperforms the IHAUPM algorithm, and even has the best results in Figure 10f. However, in terms of runtime performance, the proposed FUP-HAUIMI algorithm outperforms the other algorithms. Thanks to the efficient FUP concept and the AUL-structures, the runtime of the FUP-HAUIMI can be greatly reduced. From the above results, we can thus conclude that although extra memory usage is required and more candidate patterns are checked by the designed FUP-HAUIMI algorithm, this latter can still achieve better efficiency and effectiveness in most cases except for a very sparse dataset with long transactions or for a very dense dataset. ### Scalability

In this section, the scalability of three algorithms were compared on a synthetic dataset, which is generated by the IBM Generator [31]. The size of the database (scalability) is varied from 100 K to 500 K transactions, with a 100 K increment. The results are shown in Figure 6.1

It can be observed in Figure 11 that the proposed FUP-HAUIMI algorithm has better scalability than HAUI-Miner and IHAUPM. As \(|X|\) is increased, the runtime of the HAUI-Miner increases since the database needs to be scanned multiple times. However, the runtime of FUP-HAUIMI only slightly increases. In addition, we can see that for these datasets, the designed FUP-HAUIMI algorithm performs better than the other two algorithms in terms of runtime, memory usage, and the number of assessed patterns. Thanks to the AUL-structures, the memory usage can be greatly reduced, which can

Figure 6.2 Number of candidate patterns for various insertion ratios. be seen in Figure 11b. In addition, the FUP concept achieves good efficiency since it can reduce the number of assessed patterns, as it can be seen in Figure 11c. Based on the adapted FUP concept, the proposed FUP-HAUIMI algorithm can evaluate fewer patterns and the correctness and completeness of the algorithm is ensured for mining the updated HAUIs. Generally, the proposed FUP-HAUIMI algorithm has better performance than that of the state-of-the-art batch mode HAUI-Miner algorithm and the incremental IHAUPM algorithm. ## 6 Conclusions and Future Work

High average-utility itemset mining (HAUIM) is an emerging topic, which is an extension of traditional high-utility itemset mining (HUIM) but takes the size of itemsets into account to evaluate the average-utility of each itemset. Most HAUIM algorithms only perform in batch mode. When the size of the database is changed, the updated database must be scanned again to obtain up-to-date information. This is a costly approach since previously discovered information and the runtime to find that information is wasted. In this paper, we utilize an average-utility-list (AUL)-structure to keep the necessary information for the updating process. In addition, the adapted FUP concept is useful to reduce the number of candidate patterns for incremental mining. Thus, the developed FUP-HAUIMI algorithm can achieve better performance than that of the state-of-the-art batch-mode HAUI-Miner and the incremental IHAUPM algorithms in terms of runtime, memory usage, number of candidate patterns and scalability. In addition to transaction insertion, transaction deletion or transaction modification for HAUIM are also the emerging topics in dynamic data mining.