# MAPSKEW: Metaheuristic Approaches for Partitioning Skew in MapReduce
## 3 Results and Discussion  
### Balancing  
As shown in Table 1, the metaheuristics reduced the skew by up to 96.5428%. Local and Stochastic Beam Search Achieved great results with threshold percentage being a major factor while K and temperature being not so relevant at a first sight. To improve our investigation about the most relevant attribute, in Figure 7 we set the number of iterations to 1000 and analyze the threshold and number of candidates per iterations. Every time the threshold reach 20% the difference between partitions suffers a huge drop, especially when only one candidate is selected per iteration. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Method** & **Threshold** & **Iterations** & **K** & **Difference between Partitions** \\ \hline Base Hash & none & none & none & 1938 \\ local beam search & 20 & 3000 & 5 & 67 \\ local beam search & 20 & 5000 & 1 & 67 \\ stochastic beam search & 20 & 3000 & 1 & 68 \\ local beam search & 20 & 1000 & 9 & 69 \\ local beam search & 30 & 1000 & 9 & 69 \\ local beam search & 20 & 5000 & 9 & 69 \\ local beam search & 20 & 1000 & 5 & 69 \\ stochastic beam search & 30 & 5000 & 1 & 69 \\ stochastic beam search & 20 & 3000 & 9 & 69 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The ten best balancing results compared with the base hash approach. In terms of balancing, Simulated Annealing achieved the worst results among the three metaheuristics, as shown in Table 2. The configuration with the best result, representing about 79% decrease in partitions size, is slightly worse than the worst result of Stochastic Beam Search. However, the worst result of the metaheuristics is still better than the base hash partitioning method, meaning that even the slightly change may help reduce the existent skew. It is important to notice that the Simulated Annealing configurations with a threshold of 20% or 30% achieved better results than the ones with a threshold of 5% or 10%. It is clear that, in terms of skewness reduction, the size of the threshold is more important than the number of iterations or the number of candidates per iteration (K). Furthermore, it would be possible to test with even less iterations to reduce the overhead in this particular scenario, although it does not seem to be necessary. It would also be interesting to try other threshold values between 10% and 20% to see how those would fare in the table. \begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Method** & **Threshold** & **Iterations** & **K** & **Difference between Partitions** \\ \hline Stochastic Beam Search & 5 & 1000 & 1 & 397 \\ Simulated Annealing & 30 & 5000 & none & 401 \\ Simulated Annealing & 30 & 1000 & none & 415 \\ Simulated Annealing & 20 & 1000 & none & 430 \\ Simulated Annealing & 20 & 5000 & none & 431 \\ Simulated Annealing & 30 & 3000 & none & 431 \\ Simulated Annealing & 20 & 3000 & none & 448 \\ Local Beam Search & 5 & 3000 & 1 & 513 \\ Local Beam Search & 10 & 5000 & 1 & 568 \\ Local Beam Search & 10 & 1000 & 1 & 570 \\ Local Beam Search & 5 & 1000 & 1 & 634 \\ Local Beam Search & 5 & 5000 & 1 & 688 \\ Simulated Annealing & 10 & 3000 & none & 917 \\ Simulated Annealing & 5 & 1000 & none & 1339 \\ Simulated Annealing & 5 & 5000 & none & 1340 \\ Simulated Annealing & 10 & 1000 & none & 1432 \\ Simulated Annealing & 5 & 3000 & none & 1648 \\ Simulated Annealing & 10 & 5000 & none & 1668 \\ Base Hash & none & none & none & 1938 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Simulated Annealing compared to Base Hash and the worst Stochastic and Local Beam Search. Figure 7: Comparison of local beam search between threshold and number of candidates per iteration fixing the number of iterations in 1000. Local Beam Search performs better than Stochastic Beam Search when tested with a sufficient large threshold percentage and enough number of iterations.