# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 2 Right-Hand Side Expanding Algorithm
### Transaction Set Preprocessing
### Comparison of Algorithm Running Time with Solution Space Size

From the above experiment, a reduced transaction set was acquired from each original transaction set after the support threshold was given, and the dimension was also reduced. Therefore, the reduced dimension would vary with the support threshold, and so would the algorithm running time. The algorithm was proposed to implement the standalone operation of big data transaction sets. For the same transaction set, the reduced dimension would be increased if the support threshold was reduced, and as a result, the solution space would present an exponential (base number: 2) increase. If the algorithm running time was also increased according to an exponent with a base number of 2, the algorithm running time would experience explosive growth with the increase in dimension, which, obviously, deviated from the intention of this study. To this end, the largest transaction set _kosarak_ was experimented under different thresholds for five times. The dimension reduced grew from 42, reaching as high as 431, and the acquired number of MFIs and algorithm running time are as seen in Table 4. The data showed that the algorithm running time did not present exponential growth with the increase in dimension. The solution space size was incomparable to the algorithm running time in dimension. As the algorithm ran for 238.9 s under the dimension of 42, the dimension-dependent \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Support Threshold** & **0.0127** & **0.0063** & **0.0040** & **0.0029** & **0.0024** \\ \hline Dimension reduced & 42 & 106 & 212 & 328 & 431 \\ Number of MFIs obtained & 65 & 212 & 467 & 876 & 1265 \\ Algorithm running time (s) & 238.9 & 1054.2 & 2962.1 & 6714.2 & 12,645.8 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Testing on _kosarak_ with a different support threshold. exponential growth curve of solution space took the point (42, 238.9) in the plane as the starting point, and the fitted curvilinear contrast relation between the growth curve of solution space and actual algorithm running time is as shown in Figure 4. Obviously, when the solution space showed exponential explosive growth (red line in the figure) with the dimension, the algorithm running time was under a slow growth trend (blue line with red circle, the experimental data are shown at the red circles). As the algorithm running time did not present exponential growth with the dimension (i.e., it did not experience explosive growth), the algorithm was feasible for the standalone calculation of high-dimensional properties of big data transaction sets. ### Comparison of Algorithm Running Time with Traditional Exact Algorithm

The Apriori and FP-Growth algorithms were the two most classical accurate algorithms for mining association rules. PF-Growth was recognized to be faster than Apriori. However, PF-Growth was sensitive to the dimensions of the transaction set. Even the running time is unacceptable for mining the small transactions set listed in Table 2, but the smallest dimension of the transaction set listed in Table 2 is only 75. In order to investigate quantitatively the running time of the algorithm, we extracted a small part of the Accident transaction set on average, such as 100, or 200, or 300 transactions, etc. Each transaction captures only 10%, or 20%, or 30% at the beginning of each transaction. In this way, small transaction sets with different transaction numbers and dimensions are used to test the running time of the PF-Growth algorithm. The dimensions of each transaction set are listed in Table 5. The rows represent the different number of transactions, and the columns represent the percentage of each transaction captured. These transaction sets were used to test the PF-Growth algorithm, and the running time of PF-Growth is shown in Table 6.

Figure 4: Solution space size compared with the algorithm running time.