# Maintenance of Discovered High Average-Utility Itemsets in Dynamic Databases
## 4 Proposed FUP-HAUIM Algorithm with Transaction Insertion
### The Adapted Fast Updated Concept
Thus, we can obtain that \(auub(X)^{U}=auub(X)^{D}+auub(X)^{d}<(TU^{D}+TU^{d})\times\delta\). Corollary 4: _An itemset \(X\) remains a non 1-HAUUBI in (\(U\)) if it appears in Case 4, which can be directly ignored since it would not affect the final rules._  
Based on the above lemmas, proofs, and corollaries, the downward closure property of the \(auub\) model can still hold for incremental mining. Thus, the discovery of the updated 1-HAUUBIs is correct and complete. The FUP-HAUIIMI algorithm initially constructs the AUL-structures of 1-HAUUBIs based on the original database. The AUL-structures of all items in the inserted transactions are also obtained, which can ensure the completeness and correctness of the designed maintenance approaches. When some transactions are inserted into the original database, the designed FUP-HAUII algorithm first divides the HAUUBIs into four cases, and the itemsets of each case are then, respectively, maintained and updated by the designed procedures. After that, the \(k\)-HAUUBIs are then checked to find their actual \(k\)-HAUIs. The pseudocode of the developed FUP-HAUII algorithm is provided in Algorithm 1. ```
Input:\(D\), the original database; \(utable\), a unit profit table; \(d\), inserted transactions; \(\delta\), minimum average-utility threshold; \(D.AULs\), the AUL-structures of \(D\). Output: the set of high average-utility itemsets. 1 foreach\(T_{q}\in d\)do
2 foreach\(X\subseteq T_{q}\)do
3 build\(X.AUL\);
4\(d.AULs\leftarrow\cup X.AUL\);
5
6 Merge(\(D.AULs\), \(d.AULs\));
7
8 foreach\(X\in U.AULs\)do
9 if\(\frac{X.in\_sum}{|X|}\geq(T\textsl{U}^{d}+T\textsl{U}^{D})\times\delta\)then
10\(HAULs\gets HAULs\cup X\);
11 if\(\frac{X.tmu.sum}{|X|}\geq(T\textsl{U}^{d}+T\textsl{U}^{D})\times\delta\)then
12\(exAULs\gets null\);
13 forach\(Y\) after \(X\) in \(UAUL\)do
14\(exAULs\gets exAULs+\textbf{Construct}(X.AUL,Y)\);
15
16 Merge(\(X,exAUL\));
17
18 for\(X\in U.AULs\)do
19 if\(\frac{X.in\_sum}{|X|}\geq(T\textsl{U}^{d}+T\textsl{U}^{D})\times\delta\)then
20\(HAULs\leftarrow\cup X\);
21
22 returnHAULs,UAULs. ```  
**Algorithm 1**Proposed FUP-HAUIMI algorithm  
The designed Algorithm 1 first scans the database by considering items in the newly inserted transactions to construct their AUL-structures (Lines 1-4 of Algorithm 1). After that, the AUL-structures built from the original database and inserted transactions are merged (Line 5 of Algorithm 1). Based on the merged AUL-structures, if the average-utility of an itemset is no less than the updated minimum average-utility count, it is considered as a high average-utility itemset (Lines 7-8 of Algorithm 1), and then its supersets are considered using a depth-first search according to the enumeration tree. This process is then recursively repeated until no tree nodes are generated (Lines 9-13 of Algorithm 1). In the **Merge** function, if an item does not exist in the original database (Line 4 of Algorithm 2), the original database is then rescanned to construct the AUL-structure of the item. The average-utility of the selected itemsets is then calculated (Lines 14-16 of Algorithm 1). After that, the algorithm terminates. The updated patterns have been obtained. ```
1 set\(X.AUL\gets null\);
2 set\(U.AULs\gets null\);
3 foreach\(X\in d.AULs\)do
4 if\(\frac{X.in\_sum}{|X|}\geq T\textsl{U}^{d}\times\delta\wedge X\
otin D.AUL\)then
5 scan \(D\) to obtain \(X.AUL\) from \(D\);
6 if\(\exists X\in D.AULs\wedge X\in d.AULs\)then
7 foreach element \(E_{j}\in X.AUL\)do
8\(X.in.sum\gets X.in.sum+E_{j}.in\_sum\);
9 update \(X.AUL\);
10\(X.AUL\gets E_{j}\);
11
12\(U.AULs\leftarrow\cup X.AUL\);
13
14
15
16
17
18
19
20





The **Construct** function shown in Algorithm 3 is used to determine whether the supersets of an itemset must be maintained using the set of _tids_ to generate combinations (Lines 1-3 of Algorithm 3). The information about utilities (Lines 4-6 of Algorithm 3) are updated, and the updated AUL-structures are then returned (Lines 7-8 in Algorithm 3).