## 3. PCFMIS Algorithm
### Grouping Strategy  
Data partitioning is the premise of the parallel algorithm. An effective data partitioning method can greatly reduce the data communication between different slave nodes, thereby reducing the parallel computing time. Based on the above findings, the grouping strategy (GS) of PCFMIS used to divide all the trees in original data set \(D\) into different groups is described below:  
(1) If given \(m\) slave nodes, we should divide all the trees in \(D\) into \(m\) groups, and the number of the group is denoted as \(Gnum\). For the edge (\(x\),\(y\)) in \(D\), divide (\(x\),\(y\)) into the set \(A=\{A_{k}\}\),\(k\in[1,m]\). (2) For \(T_{i}\in D\), all the edges in \(T_{i}\) may belong to several \(A_{k}\) according to (1). Take the minimum of these \(k\) as the \(Gnum\) of \(T_{i}\), \(Gnum=\min\ k\), so \(T_{i}\) is put into the group which \(Gnum=\min\ k\). Then, for \(T_{i}\), cut the edges which belong to \(A_{mink}\). Some new trees \(T_{i}^{{}^{\prime}}\) will appear after cutting edges. (3) For these new trees \(T_{i}^{{}^{\prime}}\), repeat (2) until no new trees are produced. (4) For \(T_{j}\in D\), repeat (2) and (3). (5) All the trees in original data set \(D\) are divided into different groups, and the different groups will be put in different slave nodes. **Definition 6**. : _Related Tree. Given a tree \(T=(V,E,r)\), for \(\forall(x,y)\in E\), there is \((x,y)\in A_{k}\). \(min\ k\) is the minimum of \(k\). When \((x,y)\in A_{mink}\), \(T\) is a related tree of \((x,y)\), denoted as \((x,y)\to T\). The set of \(t(x,y)\to T\) is denoted as \(\Gamma(x,y)\)._  
**Property 1**. : _According to grouping strategy, a tree in original data set only belongs to one group._  
**Property 2**. : _According to grouping strategy, if \((x,y)\in A_{k}\), all \(\Gamma(x,y)\) will be put into the group which \(Gnum=k\)._  
According to Property 1, the trees in the original data set are grouped into different groups, which can reduce the scale of the data each slave node needs to process. Although in (2), new trees may be generated during the grouping process, the new trees are trimmed and less complex than the original tree. We can conclude from Property 2, for \((x,y)\in A_{k}\), all the induced subtrees of \(\Gamma(x,y)\) containing \((x,y)\) can be found in the group in which \(Gnum=k\). So frequent induced  
Figure 1: An example tree. subtrees of \(\Gamma(x,y)\) containing \((x,y)\) can be found only in group \(k\) instead of the whole original data set. This avoids communication between groups and realizes real parallelism. **Definition 7**. : _Frequent Edge Degree. \(D=\{T_{1},T_{2},...,T_{n}\}\), the frequent edge degree of \((x,y)\) is the number of times \((x,y)\) appears in \(D\), denoted as \(EFrq(x,y)\)._  
How to divide the edge \((x,y)\) into set \(\{A_{k}\}\) in (1) directly affects the \(Gnum\) of \(\Gamma(x,y)\). One feasible method is described below:  
Given an evenly divided interval \(A_{div}=(a_{1},...,a_{i},...,a_{m})\), \(a_{1}>...>a_{i}>...>a_{m}\), \(a_{1}=EFrq_{min}(x,y)\), \(a_{m}=EFrq_{max}(x,y)\). If \(a_{i+1}>EFrq(x,y)\geq a_{i}\), the edge \((x,y)\) is divided into \(A_{i}\), then \(\Gamma(x,y)\) will be put into the group in which \(Gnum=k\). For example, in Figure 2, suppose that the number of slave nodes is 3. Divide the trees \(T_{0}\), \(T_{00}\) into 3 groups \((G_{1},G_{2},G_{3})\). Given dividing interval \(A_{div}=(a_{1},a_{2},a_{3})\), \(a_{1}>a_{2}>a_{3}\). \(EFrq(a,b)\), \(EFrq(c,d)\), \(EFrq(d,f)\geq a_{1}\), \(a_{1}>EFq(h,d),EFrq(d,e)\geq a_{2},a2>EFrq(a,c)\geq a3\), so \((a,b)(c,d)(d,f)\) are divided into \(A_{1}\); \((h,d)(d,e)\) are divided into \(A_{2}\); \((a,c)\) is divided into \(A_{3}\). Take \(T_{0}\) in Figure 2 as an example. For \(A_{3}\), \(\Gamma(a,c)\) (in Figure 2) is divided into \(G3\). Then delete \((a,c)\) from \(A_{3}\) and cut \((a,c)\). For \(A_{2}\), \(\Gamma(a,c)\) (\(T\) in Figure 2) are divided into \(G2\). Then delete \((d,e)\) from \(A_{2}\) and cut \((d,e)\).