# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 2 Right-Hand Side Expanding Algorithm
### Transaction Set Preprocessing
The _Accidents_* dataset is four times larger than _Accidents_. To _Accidents_ dataset and _Accidents_* with the different support threshold, CD and DMM for _Accidents_* with 0.4 and our algorithm for _Accidents_ with 0.5. All three algorithms use single machine, that is, the number of nodes is 1. DMM was the fastest, CD was the slowest and our algorithm was in middle. However, the support thresholds they used were different. If the threshold value was small, more MFIs would be mined and it would take a longer time. To sum up, the running time is basically an order of magnitude, and each algorithm has its own advantages and disadvantages. Some are suitable for dense datasets, while others are for long transaction data sets. Under the limitation of computer hardware, it is feasible to select the proposed algorithm which was executed on single notebook computer. ## 5 Discussion, Conclusion, and Expectation

According to the algorithm theory stated in this study, the transaction sets should be visited during the MFI searching. Therefore, the larger the volume of transaction sets, the longer the time needed by the algorithm running. The volume of the transaction set is the product between the quantity of transactions and average transaction length. As the Expanding Operation needs to add items, the greater the dimension of the transaction set, the longer the time needed by the algorithm running. However, in the experiment on the 10 transaction sets, the reduced dimensions of both _pumsb_star_ and _pumsb_ are no more than 63, which are small compared with those of other transaction sets in the table, but the two transaction sets take the longest time (at least 12 h). The reduced dimension of _T40I10D100K_ is the maximum (545), but it takes the least time, about 10 min. Moreover, the quantity of transactions and average transaction length in _T40I10D100K_ are greater than those in _pumsb_star_ and _pumsb_, and the quantity of transactions is even more than twice of those in _pumsb_star_ and _pumsb_. This is just like picking fruits in an orchard: the larger the orchard, the longer the time needed to search it once, but the experimental data show that this is not the case. Then, is it the case that the more the fruits, the longer the time needed? However, the experimental data in Table 3 show that the quantity of MFIs found in _T40I10D100K_ is larger than those found in _pumsb_star_ and _pumsb_. Is this related to the length of MFIs found? Even if the average length of MFIs found in _T40I10D100K_ is multiplied by 10 in order that it is equivalent to the average length of MFIs found in _pumsb_star_ and _pumsb_, the calculation time will also be tenfold. Even so, the time spent is less than 1/10 of the time spent by _pumsb_star_ and _pumsb_. On the basis of the above analysis, there should be only one possibility: the main factor influencing the algorithm running time is neither the volume of transaction set nor the quantity of MFIs found, but it is correlated with the complexity of MFIs found. The complexity of MFIs does not have a linear relation with their length. Instead, the two present a growth relation greater than the linear growth relation. Whether this relation is an exponential relation and what the exponential relation (base number) remains to be further explored. From another side, this indicates that the algorithm running time is not sensitive to the volume of the transaction set, so the algorithm is practical for big data. Given this, can we understand it that the algorithm spends the time mainly in \"picking fruits\" but not \"finding fruits\"? From this angle, does it mean that the algorithm spends most of the time in acquiring the optimal solution with the excellent optimization path? The long algorithm running time is ascribed to the large quantity of MFIs but not to the large volume of transaction set or the great dimension of the reduced transaction set.