# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 2 Right-Hand Side Expanding Algorithm
### Transaction Set Preprocessing
\begin{table}
\begin{tabular}{c c c c c c} \hline  & **100** & **200** & **300** & **400** & **500** \\ \hline
10\% & 15 & 16 & 17 & 17 & 17 \\
20\% & 22 & 24 & 25 & 26 & 24 \\
30\% & 29 & 31 & 30 & 33 & 31 \\ \hline \end{tabular}
\end{table} 
Table 5: Dimensions of extracted _Accidents_. Since FP-Growth algorithm mined frequent itemsets and proposed algorithm mined maximal frequent itemsets, it had been verified that the results of FP-Growth were indeed subsets of the maximal frequent itemsets mined by proposed algorithm. Table 6 reflects that the FP-Growth algorithm was not sensitive to transaction number but sensitive to dimension. When the dimension grown from 15 to 29, the FP-Growth had a longer running time than the exponential growth. By comparison, the proposed algorithm mined the full size set of incident transactions in only 8530.40 s. Of course, the proposed algorithm had fewer optimization targets, while FP-Growth had more optimization targets. The former was the maximal frequent itemsets, while the latter is the frequent itemsets, and the number of maximal frequent itemsets was less than the number of frequent itemsets. ### Comparison with FPMax, CD, and DMM

Since parallel algorithms were very promising in solving big data mining, we make a simple comparison between the proposed algorithm and several well-known parallel algorithms, which are FPMax algorithm [38], Count Distribution algorithm [37], and DMM algorithm [40]. Although PMM algorithm [39] was also an excellent parallel algorithm and DMM was better than PMM algorithm overall, we do not compare with PMM. In Section 4.2, we present some experimental results on 10 public datasets. Some of these datasets have also been reported in the literature [37; 38; 40]. We picked the experimental results data to the same dataset as Table 7. Some figures were estimated from reported graphs, which gave a rough idea of algorithm performance. With regard to the _Class_ dataset and _Mushroom_ dataset, the experimental results of FPMax and our algorithm had the same support thresholds of 0.95 and 0.52. The running time of the algorithm is listed in Table 7. FPMax is faster than the proposed algorithm, but the former was conducted using a cluster of computers, while the latter was carried out by a single computer. Of course, the hardware of the computer is also different, and the small data set leaded the running time to be haphazard. The _Pumsb_ dataset with the same support threshold 0.8 to three algorithms, CPU-time of CD algorithm was approximately 35,000 s, our algorithm was 46591.14 s. CD is great in that it executed the _Pumsb_* dataset, which is eight times larger than the _Pumsb_ dataset. However, CD was executed on an eight-node cluster calculation. The DMM execution time under the same conditions was 9000 s, which was faster than CD algorithm. Additionally, DMM was executed on an 8-node cluster calculation. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **100** & **200** & **300** & **400** & **500** \\ \hline
10\% & 13.116257 s & 18.344052 s & 26.346489 s & 40.406259 s & 44.279161 s \\
20\% & 444.653654 s & 714.085102 s & 72.977960 s & 901.212257 s & 982.893483 s \\
30\% & 7956.674653 s & \textgreater{}2.21 h & \textgreater{}2.21 h & \textgreater{}2.21 h & \textgreater{}2.21 h \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Running time of FP-Growth for the extracted _Accidents_. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & _Class_ **(0.95)** & _Mushroom_ **(0.52)** & _Pumsb_ **(*)** & _Accidents_ **(*)** \\ \hline FPMax & \textless{}0.4 s & 0.3 s & & \\ \hline  & & & 35,000 s & 28,000 s \\ \cline{3-4} CD & & & 0.8, node:8 & 0.4, node:1 \\ \cline{3-4}  & & & 9000 s & 3000 s \\ \cline{3-4} DMM & & & 0.8, node:8 & 0.4, node:1 \\ \cline{3-4} Proposed algorithm & 0.51 s & 2.3 s & 46,591.14 s & 8530.40 s \\ \cline{3-4}  & & & 0.8, node:1 & 0.5, node:1 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Running time and resources used for various algorithm on various databases.