# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 2 Right-Hand Side Expanding Algorithm
### Transaction Set Preprocessing
Each _Expanding Operation_ contained (\(m^{-}-(P+1)\)) branch recursions, where \(m^{-}\) is the dimension of the reduced transaction set (\(m^{-}<m\)), and \(P\) is the base point at which the expanding operation adds item. Thus, the time complexity of Algorithm 2, _Expanding Operation_, is \(O\) (\((m^{-}-(P+1))!\)). In comparison, the solution space of the problem is \(2^{m}\) and the time complexity of the enumeration method is \(O\) (\(2^{m}\)). We will learn in Section 4.3 that the time complexity of Algorithm 2 is much lower than that of enumeration. ## 3 Proof of Algorithm Accuracy

The solution to the optimization problem is divided into two types: an exact solution and optimized solution, both of which are feasible solutions. The corresponding algorithms can also be classified according to the solution type. For instance, in the introduction part, the algorithm acquiring the exact solution was called the exact algorithm, and the algorithm acquiring the optimized solution was called the heuristic algorithm. The exact solution refers to the optimal solution to the problem, and this solution or set of solutions is unique. Here, the solutions may be a set of feasible solutions with equivalent excellence, and the uniqueness means that this set is unique. The optimized solution may not certainly be the optimal solution, but it may also be the optimal, and its excellence is pursued as much as possible. If the solution is a set, this set may have a missing element. The exact solution to MFI mining is the set of all MFIs found by the algorithm. The itemsets in this set should not be estimates. Instead, this set is the well-determined set consisting of itemsets. The proof of algorithm accuracy aims to prove that under the given

Figure 1: Overall framework of algorithm running. transaction set and support threshold, all MFIs will be found (lack of any itemset is not allowed), and each MFI is found only once (repetition is not allowed). Given this, two problems remain to be proven: 1 any MFI can be found, which is called integrity; 2 any MFI can be found only once. The MFIs found from the pool of MFIs are not the same; this is referred to as uniqueness. ### Integrity Proof

Assuming that \(\{l_{1},\,l_{2},\,\ldots,\,l_{k}\}\) is a random MFI, the corresponding decision variable is \(X=(x_{1},\,x_{2},\,\ldots,\,x_{m-})\), and \(x_{i}\)\(\in\)[0,1]. \(x_{i}=0\) means that the item \(i\) is not a member of itemset, and \(x_{i}=1\) means that it is a member of itemset. Then,

\[\sum_{i=1}^{m-}(x_{i})=k \tag{4}\]

The above is called frequent item \(k\)-itemset. \(x_{a},\,x_{b},\,\ldots,\,x_{k}\) are set as the first, second, \(\ldots\), and the \(k\)th non-zero items from the left to right in \((x_{1},\,x_{2},\,\ldots,\,x_{m-})\), namely, \(1\leq a<b\)\(<\leq\)\(k\). According to the overall algorithm flow in Section 2.3, the Expanding Operation will be invocated for \(m^{-}\) times (the number of nested invocation times not included), where it will be invocated in the form of Expanding Operation \((\{a\},\,P=a)\) for the \(a\)th time. As shown in Figure 2, \(a<b^{-}<b<b^{+}<\ldots<k^{-}<k<k^{+}\), E-Operation ( ) represents the function of Expanding Operation. According to the principle of Expanding Operation stated in Section 2.2, the Expanding Operation is invocated by \(m^{-}\) times. When it is invocated for the \(a\)th time, it is certainly judged that items \(b\) and \(c\) can be added into the itemset. In one step, item \(b\) is added, followed by the recursive invocation of Expanding Operation \((\{a,\,b\},\,P=b)\). Similarly, the recursive invocation of Expanding Operation \((\{a,\,b\},\,c],\,P=c)\) is carried out after the addition of item \(c\) inside the Expanding Operation \((\{a,\,b\},\,P=b)\). By parity of reasoning, the recursive nesting at the deepest layer is implemented by invocating the Expanding Operation \((\{a,\,b,\,c,\,\ldots,\,k\},\,P=k)\), and \(\{a,\,b,\,c,\,\ldots,\,k\}\) is determined as the MFI.