# Right-Hand Side Expanding Algorithm for Maximal Frequent Itemset Mining
## 2 Right-Hand Side Expanding Algorithm
### Transaction Set Preprocessing  
The preprocessing of transaction set was conducted to obtain a reduced transaction set, and the original transaction set should be scanned twice. First, the appearance probability (support) of each 1-itemset was acquired. Next, all items with a probability smaller than the threshold were excluded. Thus, a new and reduced transaction set was obtained. \(D=\{T_{1},\,T_{2},\,T_{3},\,\ldots,\,T_{n}\}\) is the original big data transaction set, and \(n\) is the number of transactions in the transaction set, where \(T_{i}=\{I_{i1},\,I_{i2},\,I_{i3},\,\ldots\,\}\), (\(i=1,\,2,\,\ldots,\,n\)) represents the \(i\)th transactions of the transaction set, \(I_{ij}\) represents the \(j\)th item of \(i\)th transactions. Each transaction is a set of items is also a subset of set of all items \(I=\{I_{1},\,I_{2},\,\ldots,\,I_{m}\}\). If \(I_{ij}\) is the \(ID\) of one item and all of \(ID\) are continuously numbered together from 1, then,  
\[m=Max_{i=1}^{n}Max\{I_{i1},I_{i2},\ldots\} \tag{3}\]  
where \(m\) is the maximum \(ID\) of an item in original big data transaction set. By this way, the \(m\) is also the dimension of the transaction set because the \(ID\) is from 1, namely, the value of \(m\) directly decides the dimension of the solution space in itemset mining. For example, we assume that the itemset \(\{I_{11},\,I_{12},\,\ldots\,\}\) is \(\{1,\,2\}\), the itemset \(\{I_{21},\,I_{22},\,\ldots\,\}\) is \(\{2,\,3,\,4\}\), and the number of transaction \(n\) is 2. Then, \(m=Max\{2,\,4\}=4\), the dimension of the transaction set is 4. Under a given transaction set \(D\) with the known dimension \(m\) and support threshold (\(Support\_T\)), the pseudocode of transaction set preprocessing is expressed as seen in Algorithm 1. ```
1:\(D=\{T_{1},\,T_{2},\,T_{3},\,\ldots,\,T_{n}\}\)
2:\(D=\{T_{1},\,T_{2},\,T_{3},\,\ldots,\,T_{n}\}\)
3:\(D=\{T_{1},\,T_{2},\,T_{3},\,\ldots,\,T_{n}\}\)
4:\(D=\{T_{1



### Expanding Operation

The expanding operator adds items to frequent itemsets according to certain rules and finds the supersets of some frequent itemsets, all of which are MFIs. The expanding operator has two features: First, the given initial itemsets must be frequent because all supersets of non-frequent itemsets cannot be MFIs. Second, what the Expanding Operation finds are not all MFI supersets corresponding to the given frequent itemsets but partial MFIs. As any MFI can be obtained by expanding different frequent itemsets, the Expanding Operation only finds the partial MFIs corresponding to the given frequent itemsets, and the remaining part is obtained through the other frequent itemsets using the Expanding Operation. This ensures that each FMI is found only once. The initial frequent itemset \(T=\{I_{1},\,I_{2},\,I_{3},\,\dots\,\}\) was given, an integer \(p\) (\(0<p<m^{-}\), where \(m^{-}\) is the dimension of the reduced transaction set, namely, the total number of different items) as the reference position for the added items, and then the pseudocode of Expanding Operation was expressed as in Algorithm 2, where \(ND=\{NT_{1},\,NT_{2},\,NT_{3},\,\dots\,\}\) is the reduced transaction set, \(NT_{i}=\{Nl_{i1},\,Nl_{i2},\,Nl_{i3},\,\dots\,\}\) and \(i=1,\,2,\,\dots\,\), \(n^{-}\) are the transactions in the transaction set, and \(n^{-}\) is the number of transactions in the reduced transaction set (\(n^{-}<n\)). The operation contained four \"for\" loops (nested loops excluded). In the first \"for\" loop, a frequent itemset \(T\) was expressed by a decision variable (\(x_{1},\,x_{2},\,\dots\,\), \(x_{m-}\)). \(x_{i}=0\) means that the item \(i\) was not a member of the itemset. If \(x_{i}=1\), the item \(i\) is a member of the itemset. The second \"for\" loop acquired all single items that could be added into the given frequent itemset, and after the addition, the itemset was still a frequent itemset. In the third \"for\" loop, the number of single items was calculated.