# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 2 Right-Hand Side Expanding Algorithm
### Transaction Set Preprocessing
If it was equal to the number of items in the frequent itemset, the given frequent itemset was namely an MFI, and then this itemset was returned. Otherwise, the fourth \"for\" loop should be executed: An addable single item was added rightward from point \(P\) by turns. The values of the given initial frequent itemset \(T\) and base point \(P\) were reset once a single item was added, followed by the recursive invocation of Expanding Operation itself. After all recursive nested structures were returned, all MFIs corresponding to the original given frequent itemset were found. As the operator only added the items at the right-hand side of point \(P\) (items with \(ID\) value greater than the \(p\) value) each time, the algorithm was named right-hand side expanding (RHSE) algorithm. ```
Input:\(T=(I_{1},I_{2},\dots)\), \(P\) Output: A group of maximal frequent itemsets \((x_{1},x_{2},\dots,x_{m})=(0,0,\dots\.0)\); \((e_{1},e_{2},\dots\.e_{m})=(0,0,\dots\.0)\); for \(i=1:\ 1\ T\!\) do \(x_{(i)}=1\);  end for for \(i=1:\ n^{-}\) do  if \(T\subseteq NT_{i}\) then  for \(j=1:\ 1 NT_{i}\!\) do \(e_{(Nij)}=e_{(Nij)}+1\);  end end end \(e\_item\_number=0\); for \(i=1:\ n^{-}\) do  if \(e_{(0)}/(n^{-})>Support\_T\) then \(e_{i}=1\); \(e\_item\_number=e\_item\_number+1\); else \(e_{i}=0\);  end end if \(e\_item\_number=1T\!\) then  Adds \(T\) into group of maximal frequent itemset; else  for \(i=P+1:\ n^{-}\) do  if \((x_{i}=0)\&(e_{i}\
eq 0)\) then  Expanding Operation (\(T\cup\{i\}\). \(P=\{i\}\));  end end
```

**Algorithm 2**Expanding Operation (\(T\), \(P\))

### Overall Framework of Algorithm Running

With this Expanding Operation, it is only necessary to reasonably organize and alternately give the initial frequent itemset of the Expanding Operation, which is then invocated. Thereafter, all MFIs of the given support threshold can be found. Under the overall framework of algorithm running, a reduced transaction set was first obtained after the preprocessing. During the preprocessing, all frequent 1-itemsets were acquired, which were set as the initial itemset alternately. Items were added by invocating the Expanding Operation, and then a group of MFIs corresponding to each frequent 1-itemset could be found. When placed together, these groups were the set of MFIs discovered by the algorithm. These MFIs were neither repeated nor omitted, being the exact solution but not the optimized solution to the problem. The overall framework of algorithm running was expressed by a block diagram in Figure 1, where \(I_{1}\), \(I_{2}\),..., \(I_{m-}\) are the \(m^{-}\) frequent 1-itemsets acquired in the preprocessing of the transaction set, which aimed to obtain a reduced transaction set, and \(m^{-}\) is the dimension of the reduced transaction set. As the dimension of the original transaction set is \(m\), the dimension of the reduced transaction set is expressed by \(m^{-}\), and \(m^{-}<m\). The \(m^{-}\) frequent 1-itemsets were set as the initial itemset of Expanding Operation, namely, \(I_{i}\), and the base point \(P=i\), (\(i=1.2\),..., \(m^{-}\)) was given in turn. The Expanding Operation was then invocated. Subsequently, several MFIs were acquired and called the group of MFIs, and these groups of MFIs finally formed a larger pool of MFIs. This larger pool of MFIs was an exact solution to the problem, and it was a set of MFIs. ### Complexity Analysis

The time complexity of the proposed algorithm RHSE was analyzed with respect to Algorithms 1 and 2. Algorithm 1 was used to generate the reduced transaction set, which requires scanning the transaction set twice. \(n\) is the number of transactions in transaction set, and let \(L_{i}\) be the average number of items in the transaction (itemsets). Thus, the time complexity of this task is \(O\) (\(n\times L_{i}\)). Algorithm 2 is the _Expanding Operation_ with an initial itemset and position point.