# MAPSKEW: Metaheuristic Approaches for Partitioning Skew in MapReduce
## 2 Materials and Methods
### Problem Definition  
As previously discussed in Section 2.1, MapReduce is a parallel computational model composed of a set of machines to process large amounts of data by its division between the machines. However, the division of the data may entail an unbalanced partitioning, also known as the partitioning skew. This problem has many several causes. Among them, we highlight the skewed key frequencies, the keyed key sizes and the skewed execution times. Except for the skew caused by the processing time of each key, which depends on the complexity of the reduce function, the data skew problem in MapReduce architectures can be addressed through of the data balancing between the cluster machines. The following definition will present the problem of finding an optimal partitioning as an optimization problem. **Definition 1**. : _Optimal partitioning of a dataset Let:_  
* _C A cluster of machines._
* _D A dataset._
* \(t\) \(=<k,v>\) _a pair consisting of a key k and a value_ \(v\) _obtained from_ \(D\)_._
* \(p_{i}=\{t_{1}=<k_{1},v_{1}>,t_{2}=<k_{2},v_{2}>,\ldots,t_{m}=<k_{m},v_{m}>\}\) _a partition consisting of a set of pairs_ \(t\)_._
* \(P=\{p_{1},p_{2},\ldots,p_{n}\}\) _a partitioning of_ \(D\) _where_ \(n\) _is the number of partitions._
* \(T(p_{i})=\{|p_{i}|\}\) _a function that returns the size of a partition. The size of the partition is equal to its cardinality._
* \(F(P)=\{\max\{T(p_{a})-T(p_{b})\}\mid p_{a},p_{b}\in P\}\) _a function that returns the unbalance of a partitioning_ \(P\)_. The unbalance of_ \(P\) _is defined as the biggest difference of the sizes of a pair of partitions in_ \(P\)  
Figure 5: Example of a graph with 3 Cliques. \(R=\{P_{1},P_{2},\ldots\ P_{w}\}\) the set of possible partitionings of \(D\) in \(n\) partitions. \(P_{opt}\) is the optimal partitioning of \(D\) if and only if \(F(P_{opt})\leq F(P_{y})\), \(\forall P_{y}\in R\), i.e., \(P_{opt}\) is the partitioning with the smallest unbalance among all partitionings of \(R\). As we have a definition of an optimal partitioning of a dataset, we can find it by searching the one with the smallest unbalance among the set of all possible partitionings. Although this method ensures the optimal partitioning, it is computationally expensive, since the number of partitionings of a dataset is exponential regarding its cardinality. Another method for finding the optimal partitioning is to use a greedy algorithm to find the smallest partition \(p^{\prime}\in P\), such that \(T(p^{\prime})\leq T(p)\), \(\forall p\in P\), in the moment that every element of the dataset arrives at the system. However, this method may fail to achieve good results depending on the order that the data is allocated to the partitions. Before presenting the method proposed in this work, we will show the definition of neighboring partitions. **Definition 2**. : _Neighboring Partitions. Let \(P_{i}\), \(P_{j}\) two partitions. \(P_{i}\) and \(P_{j}\) are neighboring partitions if and only if they differ by the allocation of only one key or the exchange of the allocation of two keys, i.e., they are identical except for a key \(k\) such that \(k\in p_{a}\) in \(P_{i}\) and \(k\in p_{b}\) in \(P_{j}\) or they are identical except for the keys \(k_{1},k_{2}\) such that \(k_{1}\in p_{a}\), \(k_{2}\in p_{b}\) in \(P_{i}\) and \(k_{1}\in p_{b}\), \(k_{2}\in p_{a}\) in \(P_{j}\)._  
Please note that a possible solution for finding the optimal partitioning lays in creating a random partitioning \(P\) and verifying if one of its neighboring partitionings \(P^{\prime}\) has a better balancing than \(P\) and repeat this process using \(P^{\prime}\) as the initial partitioning. This process may be repeated a finite number of iterations in order to find a good partitioning. This strategy is similar to the execution of the Hill Climbing metaheuristic. Although this process may return good partitionings, it may return local optima results depending on the initial partitioning.