# Incremental Algorithm for Association Rule Mining under Dynamic Threshold
## 3 Literature Review
### Incremental Problem  
Data within a database are bound to change continuously. Simultaneously, the knowledge reflects the state of the database at the time of mining. Changes that take place in the data signify the losing potential for the knowledge to reflect the database. Therefore, updating discovered knowledge is an important task to ascertain that knowledge continues to reflect the state of the database. This strategy of updating the existing knowledge is called incremental learning within the search domain. Although a substantial number of methods have been proposed to overcome this incremental issue, they tend to display certain shortcomings, including time consuming, rebuilding knowledge, and selective manipulation operations. As the databases are manipulated by time, the mining process becomes more complex than the mining of static dataset. Several problems may arise due to changes in the database, such as the generation of candidate itemset, and the scanning of the original database to validate the frequency of an itemset after database manipulation. The primary purpose of an incremental approach is to update the existing knowledge, so as to reflect the updated database state. This process should be carried out without the need to rebuild knowledge from scratch and without need to scan the entire database. Fast Update Algorithm (FUP): [PERSON], [PERSON], [PERSON], and [PERSON] (1996) initiated the first algorithm in the incremental ARM field area, known as fast update algorithm (FUP) [33]. This algorithm efficiently updates the existing association knowledge from the updated database. The \(FUP\) is similar to the Apriori algorithm, and it enhances the Apriori in generating a solution for issues related to incremental mining. Nevertheless, this \(FUP\) algorithm processes only recently added transactions on the manipulated database. Simply put, assume \(DB\) as the original database that requires data mining, while database with transactions added to it after mining is marked as \(db\). Now, \(DB+\) refers to both \(db\) and \(DB\). The \(FUP\) algorithm mines only \(db\). Consider \(x\) is an itemset, so \(x\) has a chance to be frequent or perhaps not in one or both of the \(DB\) and \(db\) databases. In this case, as tabulated in Table 1, \(x\) has four possibilities. As shown in Table 1, the itemset has four possibilities for an \(x\) itemset to be frequent. In the first case (1-Frequent), \(x\) is frequent in both \(DB\) and \(db\), while in case 4 (4-Infrequent), \(x\) is infrequent in both databases; signifying nil issue for both cases. As for the other two cases, the \(FUP\) has to determine the support for the itemset over the entire database. The worst case is block 3, where the algorithm has to rescan the entire database to ascertain if the itemset is frequent or infrequent throughout the databases. Here, the \(FUP\) does not reduce the database scanning frequency. In the initial pass, the \(FUP\) scans the \(db\) to calculate the support count of each 1-itemset. After determining the support count of itemset in \(DB\), the support of an itemset \(x\) is easily calculated if \(x\) is in block 2. If \(x\) appears in the third set, the whole \(DB\) must be scanned again to count the support of item \(x\). The frequency of scanning cannot be reduced in \(FUP\) because all DBs demand multiple rescanning. Many studies have looked into the issue of discovery of ARM incrementally. One approach refers to \(NFUP\)[34] that serves to enhance the \(FUP\) algorithm. However, it targets only new transactions. The \(IMSC\)[35] is another approach that is meant to improve the \(FUP\) algorithm by addressing the constantly changing support threshold. The popular techniques in light of ARM algorithms, particularly Apriori-like algorithms, reflect downward closure in building an itemset. The \(MAAP\)[36], however, takes a different approach to build the frequent itemset.