# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 2 Right-Hand Side Expanding Algorithm
### Transaction Set Preprocessing
Hence, the MFI \(\{l_{1},\,l_{2},\,\ldots,\,l_{k}\}=\{a,\,b,\,c,\,\ldots,\,k\}\) will be certainly found. If any MFI without loss of generality can be found, all MFIs can be too, so this algorithm ensures the high integrity of the solution set. Of course, not only Expanding Operation \((\{a,\,b\},\,P=b)\) will be invocated inside Expanding Operation \((\{a\},\,P=a)\), but Expanding Operation \((\{a,\,c\},\,P=c)\) may also be parallelly invocated. Therefore, the finally found MFI after the ending of Expanding Operation \((\{a,\,c\},\,P=c)\) will contain \(a\) and \(c\) but not \(b\), which is another MFI, but this is not contradictory with the hypothetical proposition to be prov

Figure 2: Recursive nested structures of Expanding Operation \((\{a,\,b\},\,P=a)\). ### Uniqueness Proof

According to the overall algorithm framework and item addition rules of Expanding Operation, each time the Expanding Operation adds one item since one frequent 1-itemset, it will be recursively invocated by itself once again or find the other items that can be added. The discovery process of an MFI is as shown in Figure 3a. The top-down sequence of nodes in the figure denotes the sequential order of item addition, the left or right position of each node represents the _ID_ value of item, and the left-to-right direction is the increasing direction of _ID_ value. Given this, the root nodes are located at the upper left corner and leaf nodes at the lower right corner, and this path forms a branch. The set of _ID_ values of all nodes on one branch corresponds to one frequent itemset, which may be maximal or not. At each root node, multiple branches may grow, so as to form a tree, as shown in Figure 3b. The _ID_ values of all nodes on one branch from root nodes to leaf nodes constitute a frequent itemset, and all MFIs on one tree form a group of MFIs, as mentioned in Section 2.3. As stated in Section 2.3, each frequent 1-itemset can serve as the root node to grow a tree. In Figure 3c, all green nodes can be root nodes to grow a tree. For the conciseness of this diagram, the tree growing out of green nodes was not drawn. Many trees form a forest, corresponding to the pool of MFIs in Section 2.3. Therefore, to prove that all MFIs are different in the pool of MFIs, it is only necessary to prove that only one branch, but not a second branch, corresponds to each itemset. This proposition was proven through the reduction to absurdity. Assume that an MFI (\(MFI_{1}\)) is determined for a branch (\(Branch_{1}\)), and this MFI has a corresponding relation with another branch (\(Branch_{2}\)). According to the right-hand side item addition rules of Expanding Operation, only items with greater _ID_ values are added, and then the difference (difference value of x

Figure 3: (a) A branch is a frequent itemset; (b) a tree is a group of MFIs; (c) the forest is the pool of MFIs. coordinates) of \(ID\) values between two nodes connected by any edge in \(Branch_{1}\) is certainly greater than 1, while the difference value of y-coordinates is bound to be 1. In order for \(Branch_{2}\) and \(Branch_{1}\) to correspond to the same itemset, the nodes of \(Branch_{2}\) should be different from those of \(Branch_{1}\) only in y-coordinates; otherwise, their horizontal projections will be different, so will the corresponding itemsets. If the nodes of \(Branch_{2}\) are different from those of \(Branch_{1}\) only in the upper or lower position, there will certainly be such an edge in \(Branch_{2}\) that the difference value of y-coordinates of two nodes it connects is equal to zero or greater than 1 because the difference of \(ID\) values between two nodes connected by the edge in \(Branch_{1}\) is certainly greater than 1, the difference value in y-coordinates is equal to 1, and the two branches must share the same root nodes. If the difference value is equal to zero, the Expanding Operation adds two items once. If it is greater than 1, the Expanding Operation enters recursive invocation without adding any item.