# MapReduce Algorithm for Location Recommendation by Using Area Skyline Query
## 3 MapReduce-Based Area Skyline
#### MRGASKY Algorithm
Next, we compare \(x_{13}\) and \(x_{34}\), and save \(p_{3}\) into the stack. Follow the same procedure until all eight points are encountered. Finally, point \(p_{1}\), \(p_{3}\) and \(p_{7}\) are saved into the stack. point \(p_{2}\), \(p_{4}\), \(p_{5}\), \(p_{6}\) and \(p_{8}\) are deleted from the stack. **Step 2.2**: For the \(i\)th column, we compute the distance of the points which are deleted from the stack. Specifically, we bisect the adjacent left points to determine the proximate intervals [21] on \(x\)-axis. The interval \([a,b]\) (\(a,b\in\mathbb{Z}\) and \(a\leq b\)) of the left point \(p_{i}\) after step 2.1 process determines the dominated areas of point \(p_{i}\). Figure 10 shows an example of step 2.2 process. \(p_{1}\), \(p_{3}\) and \(p_{7}\) are the left points of step 2.1. We bisect \(p_{1}\), \(p_{3}\) and \(p_{3}\), \(p_{7}\) to calculate \(x_{13}<0\) and \(x_{37}=5\). The intervals of points \(p_{3}\) and \(p_{7}\) are  
Figure 8: An Example of Maintaining Point \(p_{j}\). Figure 7: An Example of Deleting Point \(p_{j}\). Figure 4:0 An Example of Step 2.1.  
and \([x_{37},8]\). It means that the point \(p_{3}\) dominates points \(p_{1},p_{2},p_{4}\) and \(p_{5}\). Points \(p_{6},p_{8}\) are dominated by point \(p_{7}\). In the obvious way, we can compute the distance of all grids in the map. The algorithm of Reduce function is illustrated in Algorithm 2. The input of this step is the \(key-value\) pairs. The \(key\) is the column ID, and the \(value\) is the distance calculated in the Map function. The outputs are the area skyline objects such as the shaded grids shown in Figure 4:1  
```
1:The results of the sorted and shuffle phase
2:Area skyline objects
3:for each point sorted by \(x\)-coordinate in the same column do
4:if\(x_{ij}>x_{jk}\)then
5: pop the point \(p_{j}\) from the stack
6:endif
7:endfor
8:for all un-popped points which are sorted by \(x\)-coordinate do
9: calculate the proximate interval of each point on \(x\)-axis
10: calculate the Euclidean Distance of the points in the interval
11:endfor
12://remove the dominated grids
13:for the record \(r_{i}\) of the Euclidean Distance for all types of each grid do
14:if\(r_{i}<r_{j}\)then
15: remove the dominated grid from the record
16:endif
17:endfor
18:return skyline objects
```  
**Algorithm 2** Reduce Function for Step 2 Process  
We demonstrate the complete results of the step 2 process of type \(F1^{+}\) in Figure 4:2 Note that for the facility type, \(F2^{+}\) and \(F3^{-}\) can be calculated in the same process in the MapReduce framework. Intuitively, our proposed MRGASKY algorithm can implement the same process of Voronoi Diagram. However, MRGASKY is a distributed algorithm in MapReduce framework whose complexity is much smaller than the Voronoi Diagram method. Figure 4:3 An Example of Step 2.2. Figure 12 demonstrates MapReduce data flow of facility type \(F1^{+}\) and \(F2^{+}\). The input data are stored in HDFS. Specifically, they are formed as facility types \(F\), row IDs \(n\) and the values of the binary image in the same row. Next, we separate the data by row-wise and send them to the Map function. In the Map function, the data are processed by \(key-value\) pairs. The output of the Map function generates new \(key-value\) pairs, and the intermediate \(key-value\) pairs are grouped and sorted with the same intermediate keys. After sorted and shuffle phase, the grids in the same column are grouped. Similarity, the grouped data are sent to the Reduce function. The Reduce function mainly calculates the distance of every grid to the nearest facility of each type column-wise.