# Incrementally Mining Column Constant Biclusters with FVSP Tree
## 2 Method
### Initial CCB Mining
#### 2.2.2 Initial FVSFP Tree Construction  
Constructing FVSFP tree is similar to constructing FP tree. The key is iteratively inserting sample to the tree. The tree is made of nodes. The node is defined as follows:  
Struct FVSFPNode{  
Name;  
Count;  
Struct FVSFPNode* Parent;  
Struct FVSFPNode* Children[];  
**Name**: the name of the node.  
**Count**: the appearance number of the node.  
**Parent**: a pointer to the parent node.  
**Children**: one or several pointers to the whole children nodes.  
In the FVSFP tree, there are three kinds of nodes, namely, Root node, leaf node and middle node. The Root node is in the topmost level, all domains except for Children are NULL. The leaf node is in the lowest level, has no children. Middle node is the node between the leaf node and the Root node. One branch of the tree is defined as the whole nodes from Root node to leaf node. One sample can form one branch. The construction of an original FVSFP tree can be summarized in the following two steps:  
* Construct the Root node;
* Insert the samples of the original dataset sample-by-sample with Algorithm 1.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Sample No.** & \multicolumn{5}{c}{**Original Feature**} \\ \hline
2 & 0 & 1 & 1 & 1 \\ \hline
3 & 0 & 0 & 0 & 0 \\ \hline
4 & 0 & 0 & 0 & 1 \\ \hline Original feature value vector & [0] & [0 1] & [0 1] & [0 1] \\ \hline Feature value size & 1 & 2 & 2 & 2 \\ \hline New feature value range & [0] & [1 2] & [3 4] & [5 6] \\ \hline Transfromation (mapping) & 0-\(>\)0 & 0-\(>\)1-\(>\)2 & 0-\(>\)3 & 0-\(>\)5 \\  & & 1-\(>\)2 & 1-\(>\)4 & 1-\(>\)6 \\ \hline
**Sample No.** & \multicolumn{5}{c}{**Transformed Feature**} \\ \hline
1 & 0 & 1 & 3 & 5 \\ \hline
2 & 0 & 2 & 4 & 6 \\ \hline
3 & 0 & 1 & 3 & 5 \\ \hline
4 & 0 & 1 & 3 & 6 \\ \hline \hline \end{tabular}
\end{table}
Table 2: An example illustrating the feature transformation process.  
Figure 2: Illustration of incrementally mining CCB.  
```
0: Initial FVSFP tree, \(T_{o}\); Sample, \(S\); Feature number in \(S\), L.
0: Updated FVSFP tree, \(T_{o}\)
1: CurrentNode\(\leftarrow\)Root of \(T_{o}\).
2: CNodes\(\leftarrow\)CurrentNode's children nodes.
3:\(n\leftarrow\)CNodes' size.
4:for\(i\)=1:L do
5:if CNodes[j]'s name (\(1\leq j\leq n\)) is the same as S(i) then
6: CurrentNode \(\leftarrow\)CNodes[j]
7: CNodes\(\leftarrow\)CurrentNode's children
8:\(n\leftarrow\)CNodes' size.
9: CurrentNode's Count\(\leftarrow\)CurrentNode's Count+ 1.
10:else
11: Add a new node NodeN to \(T_{o}\).
12: Set NodeN's Name as S(i), Count as 1.
13: Set NodeN's Parent as CurrentNode.
14: Set NodeN's Children as NULL.
15: CurrentNode\(\leftarrow\)NodeN
16: CNodes\(\leftarrow\)CurrentNode's children
17:\(n\leftarrow\)CNodes' size.
18:endif
19:endfor
20:return\(T_{o}\)
```  
**Algorithm 1** Insert sample to FVSFP tree.  
One example illustrating adding a sample to the FVSFP tree is shown in Figure 3. Figure 3 shows the process of inserting the second sample of the original datasets in Figure 2 to the FVSFP tree with Algorithm 1. The adding process is finding common nodes, increasing common nodes' count with 1 if the sample's feature value is identical and adding new nodes otherwise.  
Figure 3: Illustration of adding a sample to the FVSFP tree. From left to right, the first tree is the tree after the first sample (\(0\;1\;3\;5\)) is inserted to the tree. The second tree is the updated tree after the first feature value ‘0’ of the second sample (\(0\;2\;4\;6\)) is inserted to the tree, because feature value ‘0’ is the same as the name of node “0”, the number of node “0” increases from 1 to 2. The third tree corresponds to the updated tree after feature value ‘2’ is inserted to the tree, because in the second level no node’s name is the same as second feature value ‘2’, thus, a new node “2” is created in the second level. The fourth and fifth trees are created in the same way as the third tree.