## 2 The Related Literature and Background
### Key Algorithms for Association Rule Mining  
Over the years, several algorithms have been developed for the efficient discovery of frequent itemsets and generation of association rules from large transactional datasets. Among these, Apriori and FP-Growth remain two of the most widely studied and implemented due to their foundational roles and contrasting strategies. Additionally, other algorithmic variants and improvements have emerged to address specific performance bottlenecks in diverse data environments.  
The Apriori algorithm, introduced by [PERSON] and [PERSON] [6], follows a breadth-first, level-wise approach to generate candidate itemsets. It is built on the Apriori property, which asserts that all non-empty subsets of a frequent itemset must themselves be frequent. This enables pruning of the search space by eliminating infrequent candidates early.  
The algorithm proceeds iteratively: it first identifies frequent 1-itemsets, then extends them to larger itemsets (k-itemsets) by joining frequent (k \(-\) 1)-itemsets. In each iteration, the database is rescanned to count support values. Once all frequent itemsets are identified, association rules are generated from them using thresholds for confidence and lift.  
Although conceptually simple and historically significant, Apriori's major drawback lies in its multiple database scans and exponential growth in candidate itemsets, which result in high computational costs for large or dense datasets [8].  
To overcome the inefficiencies of Apriori, [PERSON] et al. [7] proposed the FP-Growth (Frequent Pattern Growth) algorithm. Unlike Apriori, FP-Growth eliminates candidate generation by constructing a compact structure known as the FP-Tree, which captures itemset frequencies in a prefix-tree format.  
The algorithm starts with a scan of the database to identify frequent items and sort them by frequency. In a second pass, each transaction is mapped into the FP-tree based on this ordering. Mining then proceeds by recursively generating conditional pattern bases and constructing conditional FP-trees to extract frequent itemsets through a divide-and-conquer strategy.  
This approach significantly reduces both the execution time and memory usage, particularly for large, sparse datasets. However, managing FP-trees can be challenging when datasets contain a very large number of distinct items or low-overlap transactions.  
In addition to Apriori and FP-Growth, several alternative algorithms have been developed to address specific computational challenges in association rule mining.  
Eclat (Equivalence Class Transformation), introduced by [PERSON] [9], employs a depth-first traversal strategy combined with a vertical data format, making it efficient for dense datasets, though it can become memory-intensive when dealing with large transaction volumes.  
DHP (Direct Hashing and Pruning), a variant of Apriori proposed by [PERSON] et al. [10], uses hashing techniques to reduce the number of candidate itemsets and limit unnecessary database scans early in the mining process.  
H-Mine, tailored for high-dimensional data, organizes items into a hierarchical structure to boost performance on complex datasets [11].  
Lastly, Closet+ focuses on mining closed frequent itemsets--those that have no super-sets with the same support--thereby reducing redundancy and enhancing the efficiency of rule generation [12].  
Each of these algorithms brings trade-offs in terms of scalability, memory usage, and dataset suitability. However, Apriori and FP-Growth continue to serve as standard benchmarks due to their contrasting design philosophies and widespread implementation in modern data mining tools.