# MapReduce Algorithm for Location Recommendation by Using Area Skyline Query
## 3 MapReduce-Based Area Skyline
#### MRGASKY Algorithm  
**Step 1**: Map function mainly calculates the distance to the closest facilities of each type in the same row. **Step 1.1**: A map is firstly separated to \(n\) rows. For each row, the Map function reads the grids from both sides to calculate the distance between grids and facilities. We assume that the initial values of all grids are infinite before facilities are encountered. When facilities are encountered, the values of the grids are considered as 0. Then, the value of the next grid is updated based on the former grid plus one until the next facility is encountered. An example of 7 th row of Figure 3 demonstrates in Figure 4. The shaded grids are the facilities of \(F1^{+}\). The values of these shaded grids are 0. From left to right side, the values of the 5 th, 6 th and 8 th grids are updated to 1, 2 and 1. Similarly, we can also compute the values from right to left side. Figure 4: An Example of Step 1.1. **Step 1.2**: After calculating the values from both sides, we select the minimum value of every grid as the output of the Map function, as illustrated in Figure 5.  
Algorithm 1 shows the algorithm of Map function. The map is stored in Hadoop distributed file system (HDFS) which is formed as a binary image. Specifically, for a binary image of size \(n\times n\), \(m_{i,j}(1\leq i,j\leq n)\) is an array which includes every type of facilities in the grid of \(i\)th row and \(j\)th column. \(m_{i,j}[k](k\leq m)\) is the \(k\)th element of array \(m_{i,j}\), where m is the total number of facility types. \(m_{i,j}[k]=1\) represents the facility of \(k\)th type is inside the grid \(g_{i,j}\) and \(m_{i,j}[k]=0\) represents that there are no facilities of \(k\)th facility type inside grid \(g_{i,j}\). The Map output are the \(key-value\) pairs. The \(key\) is the column ID \(j\) and row ID \(i\) of grid \(g_{i,j}\), and the \(value\) is the distance we calculated in step 1. ```
0: A binary image
0: (key, value)=(type \(x\)-coordinate of grids. \(y\)-coordinate of grids, distance)
1:for each line in HDFS do
2: calculate the Euclidean Distance from left to right: \(dist_{left\to right}\)
3: calculate the Euclidean Distance from right to left: \(dist_{left\to right}\)
4:endfor
5:for each grid in the same row do
6: \(dist_{min}=min(dist_{left\to right},dist_{left\to right})\)
7:endfor
```  
**Algorithm 1** Map Function for Step 1 Process  
We show the results of \(key-value\) pairs after calculating step 1 process of facility type \(F1^{+}\) in Figure 6.  
**Step 2**: Again, we calculate the distance of every grid to the nearest facilities in the same column in Reduce function. **Step 2.1**: The \(key-value\) pairs of step 1 process are sorted and shuffled by column. The Reduce function reads the \(key-value\) pairs in the \(i\)th column from bottom to up and saves the values into a stack. Notice that every column is saved in its corresponding stack. We project the grids in the same column into a two-dimensional coordinate where \(x\)-axis represents the column IDs of grids, which we count them from bottom to up, and the values of \(y\)-axis are the results in step 1.2. We name all \(n\) points as \(p_{1},p_{2},...,p_{n}\). Then, we bisect the adjacent two points \(p_{i}=(x_{i},y_{i})\), and  
Figure 5: An Example of Step 1.2. Figure 6: An Example of Step 1. \(p_{j}=(x_{j},y_{j})\) where (\(1\leq i<j\leq n\)). \(x_{ij}\) is the intersection of the vertical bisector \(\overline{p_{i}p_{j}}\) and \(x\)-axis. We compute \(x_{ij}\) by formula (1): \[x_{ij}=\frac{(y_{j}^{2}-y_{j}^{2})+(x_{j}^{2}-x_{i}^{2})}{2(x_{j}-x_{i})}\] (1)  
Assume that \(p_{i}\), \(p_{j}\) and \(p_{k}\) are three adjacent points and (\(i<j<k\)). We delete \(p_{j}\) from the stack if and only if \(x_{ij}>x_{jk}\). Otherwise, we save the point \(p_{j}\) into the stack. Figures 7 and 8 illustrated the two cases whether deleting \(p_{j}\) or not. Figure 9 demonstrates an example of the step 2.1 process of 5 th column of Figure 6. Firstly, we compare \(x_{12}\) and \(x_{23}\), and delete \(p_{2}\) from the stack.