# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 4 Proposed FUP-HAUIM Algorithm with Transaction Insertion
### The Adapted Fast Updated Concept
```
Input:\(X\).AUL, the AUL-structures of \(X\); Y, the itemset Y after \(X\) in \(X\).AUL. Output:\(XY\).AUL, the AUL-structures of \(XY\). 1\(XY\).AUL\(\gets null\); if\(\exists E\in Y\).AUL\(\wedge X\).AUL.tid\(==Y\).AUL.tidthen
2\(E_{XY}\).AUL.tid\(\gets X\).AUL.tid;
3\(E_{XY}\).iu\(\leftarrow(X\).AUL + \(Y\).AUL)/2;
4 update \(E_{XY}\).tmu;
5\(E_{XY}\)\(\leftarrow\)\(<E_{XY}\).tid, \(E_{XY}\).iu, \(E_{XY}\).tmu \(>\);
6\(XY\).AUL\(\leftarrow\)\(\cup E_{XY}\). 7 return \(XY\).AUL;
```

**Algorithm 3****Construct**\((X\).AUL, \(Y)\)

## 5 Experimental Evaluation

In this section, an evaluation of the runtime, memory usage, number of patterns and scalability of the proposed algorithm is presented. The designed FUP-HAUIMI algorithm is compared with the state-of-the-art HAUI-Miner algorithm running in batch mode [22], and the state-of-the-art IHAUPM algorithm [29] running in incremental mode. All the algorithms were written in Java, and executed on an Intel(R) Core(TM) i7-6700 4.00 GHz processor with 8 GB of main memory. Windows 10 was used as operating system for running the experiments. Six datasets were used, including four real-life datasets [30] and two synthetic datasets. The simulated datasets were generated by the IBM Quest Synthetic data generator [31]. A two-phase simulation model [10] is used to generate the internal and external utilities. To describe the datasets, \(\#|\mathbf{D}|\) represents the number of transactions in the dataset; \(\#|\mathbf{I}|\) is the number of items in the dataset; **AveLen** indicates the average-length of the transactions in the dataset; **MaxLen** denotes the maximal length among all transactions in the dataset; and **Type** indicates whether the dataset is sparse or dense. Characteristics of the datasets are shown in Table 4.

Experiments were performed using various minimum high average-utility thresholds (TH) values and different insertion ratios (IR). The IR is the percentage of transactions in the original dataset that is inserted for incremental maintenance. Results are presented next. ### Runtime

In the experiments, the runtime of three algorithms was measured for various TH values and a fixed IR (=1%), as shown in Figure 5. Since the characteristics of the datasets used in the experiments are varied, different TH values are used for different datasets. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Dataset** & \(\#|\mathbf{D}|\) & \(\#|\mathbf{I}|\) & **AvgLen** & **MaxLen** & **Type** \\ \hline retail & 88,162 & 16,407 & 10 & 76 & Sparse \\ T1014D100K & 100,000 & 870 & 10.1 & 29 & Sparse \\ kosarak & 990,002 & 41,270 & 8 & 2498 & Sparse \\ T401D100K & 100,000 & 1000 & 39.6 & 77 & Dense \\ mushroom & 963 & 119 & 23 & 23 & Dense \\ foodmart & 21,556 & 1559 & 4 & 11 & Sparse \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Characteristics of the datasets. In Figure 5, it is obvious that the designed FUP-HAUIMI algorithm has better performance than the other two algorithms for the six datasets. As the TH value is increased, the runtimes of the three algorithms decrease. This is reasonable since when the TH is increased, fewer HAUIs are discovered. Hence, less runtime is required for the three algorithms. Besides, it can be seen that the designed FUP-HAUIMI algorithm remains stable for various TH values for some datasets such as Figure 5a,c,d. The reason is that, although the TH is increased, most of the knowledge was discovered for lower minimum average-utility threshold values. It is also worth to mention that HAUI-Miner is the state-of-the-art algorithm for mining HAUIs based on the _auub_ model, and that IHAUIM is the state-of-the-art algorithm for incremental HAUIM using a tree structure. Thus, it can be concluded that the designed FUP-HAUIMI algorithm performs well for handling a dynamic database with transaction insertion. This is because the designed FUP-HAUIMI algorithm only handles small parts of the inserted transactions, and some itemsets in Case 3 can be ignored. Hence, the runtime is reduced.