Frequent Itemset Mining Algorithm Based on Linear Table

Related Work

The Apriori-like algorithm is a kind of frequent itemset mining algorithm with a relatively simple structure, and the mining process adopts the method of breadth-first traversal. The IAA (Wu et al., 2009) uses a count-based and record-generated method to improve the performance of the Apriori algorithm. Yuan et al. (2017) further use an overlapping strategy to compute support for achieving high efficiency. The FP-growth algorithm (Han et al., 2000) constructs an FP-tree structure and uses depth-first traversal for mining. A new DPT algorithm (Qu et al., 2020) is proposed, which only uses a dynamic prefix tree structure and can directly output a prefix tree representing all frequent itemsets, thus avoiding the high cost of building many prefix trees. The negFIN algorithm (Aryabarzan et al., 2018) adopts the bitwise operation to extract the NegNodesets structure of the itemset and uses a set enumeration tree to generate frequent itemsets, which is pruned by the promotion method. FDM is a new algorithm based on FP-tree and DIFFset (Gatuha & Jiang, 2017) data structures, which can mine long and short patterns from dense and sparse datasets. The SS-FIM algorithm (Djenouri et al., 2017) performs a single scan of the transactional database to extract frequent itemsets, and the algorithm is less sensitive to the changes in the minimum support threshold set by the user. The dFIN algorithm (Deng, 2016) represents the itemsets through the DiffNodeset structure. The algorithm uses a hybrid search strategy to find frequent itemsets on the set enumeration tree and directly enumerates frequent itemsets without generating candidate itemsets under certain conditions. The PrePost (Deng et al., 2012) and PrePost+ (Deng et al., 2015) use a vertical N-list structure to store the key information of frequent itemsets, which calculates the support through the intersection of N-lists. In particular, the PrePost+ algorithm adopts an effective pruning strategy called Children-Parent Equivalence pruning, which reduces the search space. The Nodeset (Deng & Lv, 2014) is a more efficient data structure, it only needs pre-order or post-order encoding of each node, which makes it save half the memory compared with the N-list.