## 3. PCFMIS Algorithm
### Improvements on Parallel Algorithm
#### 3.3.2 Load Balancing  
An effective edge division strategy (EDS) is proposed in this section. If \((x,y)\epsilon A_{k}\), \(\Gamma(x,y)\) will be put into the group \(k\). The division of edges in the original data set affects the load of the slave nodes. Take the frequent edge degree as the basis for the edge division strategy. Abstract edge division strategy as a math problem, it can be described as below: Suppose that there are \(w\) different edges in the original data set, and their frequent edge degree is denoted as \(EFrq(i)\), \(1\leqslant i\leqslant w\). Record \(EFrq(i)\) in the array \(x[i]\). Divide different edges from the original data set into the set \(\{A_{k}\}\), ensuring that the sum of the frequent edge degree in each \(A_{k}\) is approximately equal. The improved parallel algorithm is called PCFMIS3. The steps of EDS are described below:  
1. Get the mean of array \(X\), \(u\)=\(\frac{\sum X[i]}{k}\). 2. Traverse the array \(X\), if \(X[i]>u\), then it is assigned separately to a group. Suppose there are \(s\) groups like that. 3. Now, the problem is translated into such a problem: divide \((w\)\(-\)\(s)\) different edges into \((k\)\(-\)\(s)\) sets, ensuring that the sum of the frequent edge degree in each group is approximately equal. 4. For the rest \(X[j]\), \(1\leqslant j\leqslant w\)\(-\)\(s\), get the mean of array \(X\), \(u^{\prime}\)=\(\frac{\sum X[j]}{k-s}\). 5. Translate the step (3) and (4) problem to 0-1 Knapsack Problem in order to solve it. An example of the EDS method is given here to show how it works: suppose that the frequent edge degree of the original data set is 50, 60, 80, 100, 150, 200, 400, 1000, and \(k\) = 3. The mean value \(u=\frac{50+60+80+100+150+200+400+1000}{3}\) = 680. As \(1000>680\), \(1000\) is assigned separately to \(A_{1}\). Now, the problem is translated into such a problem: Divide the rest of the edges into two sets, ensuring that the sum of the frequent edge degree in each set is approximately equal. Get the mean value \(u=\frac{50+60+80+100+150+200+400}{2}=520\). Translate the problem to 0-1 Knapsack Problem in order to solve it. The weights of these items are 50, 60, 80, 100, 150, 200, 400 and the backpack capacity is 520. The answer is that 50, 60, 400 make the total value biggest in the backpack. 50, 60, 400 are assigned to \(A_{2}\), and the rest are assigned to \(A_{3}\). PCFMIS3 solved the problem of load balancing and introduced the optimized compression. The flowchart of PCFMIS3 is shown in Figure 3. Three steps including two Map-reduce operations are completed during parallel computation. Step1: Calculate edge frequent degree of each edge in original tree set. In Map 1 (Algorithm 1), record each occurrence of each edge in a tree set split, which is the input of Reduce 1 (Algorithm 2). In Reduce 1, the edge frequent degree of each edge is counted out. Step 2: Cut edge and find frequent subtree. In Map 2 (Algorithm 3), trim the edges for which the edge frequent degree is less than according to the list; divide the edges into different sets according to EDS; divide the subtrees into different groups according to GS. Then which group the subtree is divided to is the input of Reduce 2. In Reduce 2, find frequent subtrees in each group. The maximal frequent subtrees of each group could be obtained. Step 3: Find the maximal subtrees of original tree set. In this step, run the frequent subtree sets maximal processing to obtain the final maximal frequent subtrees. ```
Input://key: document name //value: subtree set Output:(\(key\_edge\),1)// the key_edge is the edge in the subtree set. 1 for each edge in subtree setdo
2 \(\text{Emit}\;(key\_edge\),1)
3 end for
```  
**Algorithm 1**Map \(1\;(key,value)\)  
Figure 3: Parallel algorithm PCFMIS3 flowchart.