# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 1 Introduction
[34] used the PSO algorithm to mine frequent itemsets in a transaction set called FoodMart2000, which contained 12,100 transactions with a dimension of 34. [PERSON] et al. [35] enhanced the random search performance of the PSO algorithm and mined frequent itemsets in a transaction set with 1000 transactions and a dimension of 5. [PERSON] et al. [36] designed an artificial cell division algorithm, which was very successful in solving multipath search tasks involving search space and achieved superior effect when applied to small-scale transaction sets compared with the Apriori algorithm. Although the abovementioned algorithms have not been applied to high-dimensional big data transaction sets, the heuristic algorithm is theoretically feasible in the face of high-dimensional mass big data. Nevertheless, the solution found is an optimized solution but not an exact solution. The exact solution can be found using the exact algorithm, which, however, decomposes a task based on special computing platforms when applied to big data (e.g., Spark). Moreover, exact algorithms are based on cluster computing, which requires multiple computers. Therefore, both algorithms have their respective advantages and disadvantages when solving the big data association rule mining problem. For large-scale transactions set, parallel data mining is very promising, so a few algorithms for parallel mining association rules were proposed. The most well-known one of them is the Count Distribution (CD) algorithm [37], which is a parallel version of the Apriori algorithm. In CD algorithm, databases are initially partitioned and distributed across multiple processing nodes. The FPMAX algorithm [38] based on FP-Tree was one of the most efficient and stable mining algorithms for maximum frequent itemsets. However, for mining in dense transaction sets, FPMAX would generate many redundant recursive procedures, resulting in an additional conditional FP-tree construction overhead. Additionally, when the support was low, FPMAX would degrade the performance of superset detection due to the large global MFI-tree used for superset detection. The parallel max-miner (PMM) algorithm [39] and the distributed max-miner (DMM) algorithm [40], proposed by [PERSON] and [PERSON], are two excellent MFI mining algorithms for high-dimensional big data. Compared to most of existing mining algorithms, PMM looked ahead at each pass and prunes more candidate itemsets by checking the frequencies of their supersets. DMM has a local mining phase and global mining phase. During the local mining phase, each node mines the local database to discover the local maximal frequent itemsets, and then they formed a set of maximal candidate itemsets for the top-down search in the subsequent global mining phase. A new prefix tree data structure was developed in DMM to facilitate the storage and counting of the global candidate itemsets of different sizes. This global mining phase using the prefix tree can work with any local mining algorithm. Both PMM and DMM were implemented on a cluster of workstations, and they required very low communication and synchronization overhead in distributed computing systems. From the above analysis, we propose an exact algorithm. This algorithm does not used any computing platform, nor does it required a cluster of computers, but it could find the exact solution--all MFIs of big data transaction set within an acceptable time range. In the other word, the motivation of the algorithm proposed in this paper is to realize the MFI mining in an acceptable time range without using cluster computers for the big data with high-dimensional attributes and massive transaction numbers. The algorithm presented in this paper will contribute to the MFIM problem in the following ways. 1 The reduced transaction set is generated and used without changing the mining results.