# HI-Sky: Hash Index-Based Skyline Query Processing
## 3 Hash Index-Based Skyline Query Processing
### Hash Index-Based Skyline Query Processing
#### 3.2.4 Skyline Computation using HI-Sky
Conversely, if the GLAD of the Sky_window is not a comparison object, HI-Sky checks whether the given GLAD is identical to the GLAD of the Sky_window, and if it is not, HI-Sky moves to the next GLAD in the Sky_window and repeats the process. However, if there is a match, using the characteristics of Lemma 5, the skyline candidate is determined as either dominating or dominated, and the dominated data are removed. If data are not dominated according to the dominance test, they are stored as a skyline candidate in a Sky_window with the same GLAD. The storing is carried out in an aligned manner by entropy score for efficiency of comparison. Therefore, in the second step, data points \(A\) and \(B\) stored in GLAD 5 (0101) are used first, and \(A\) is determined as the skyline of 5 (0101), as shown in Figure 3e. When \(B\) is used first instead of \(A\) and is stored in Sky_window as a skyline candidate, we can see through Lemma 6 that \(A\) is likely to dominate \(B\), and we can thus remove \(B\) and add \(A\) to the list of skyline candidates through comparison. In the subsequent case of GLAD 7 (0111), a comparison with the skyline candidates of GLAD 5 (0101) should be performed because 7 (0111) was dominated by 5 (0101). In this process, data point \(D\) is removed from the comparison because it is dominated by the skyline candidate \(A\) of 5 (0101) as shown in Figure 3f, and there are no more data points in 7 (0111). Thus, it does not have a skyline candidate. In case of GLAD 8 (1000), as it is not dominated by 5 (0101), it is not necessary to compare it with its skyline candidate. Because dominance has not occurred between GLAD 5(0101) and GLAD 8(1000) due to dimension 2, we can skip the dominance test up to GLAD 7(0111) using Lemma 5. Therefore, data point \(G\), the only data point in GLAD 8 (1000), is defined as the skyline candidate of 8 (1000) as shown in Figure 3g. The data point \(C\) of GLAD 9 (1001) is then dominated and removed by skyline candidate \(A\) belonging to GLAD 5 (0101). The last GLAD of the GLAD_window, 12 (1100), is not dominated by 5 (0101), but is dominated by 8 (1000) through the dominance test. Therefore, it is necessary to perform a comparison with the skyline candidate \(G\) of GLAD 8 (1000), and as data point \(H\) is not dominated by \(G\), it is confirmed as the skyline candidate of GLAD 12 (1100) as shown in Figure 3h. As the GLAD and data stored in GLAD_window no longer exist, Step 2 ends, and \(A\) of GLAD 5 (0101), \(G\) of 8 (1000), and \(H\) of 12 (1100) are determined as skylines and are returned as the results of the skyline query as shown in Figure 3i. The processing of HI-Sky can be represented by the HI-Sky algorithm shown in Figure 4.  
In line 2, the GLAD_window is initialized, and in lines 3-11, HI-Sky performs data space pruning through a comparison between GLADs. If the GLAD_window is empty, the smallest GLAD will be saved immediately without comparison, as in lines 4 and 5. Otherwise, GLAD_window stores only the undominated GLAD, as shown in line 6-11, by comparing the GLAD read from HashGrid with the GLAD stored in GLAD_window. After finishing the data space pruning, HI-Sky performs the skyline computation on lines 12-35. In line 13, a Sky_window is created for each of the GLADs stored in the GLAD_window. In lines 18-23, a comparison is made between the data belonging to different GLADs. If there is no dominant relation to the GLAD according to line 18, the comparison is not performed, and if Lemma 6 is not satisfied in the comparison process, the comparison with the current Sky_window is ended as shown in lines 22 and 23. In lines 24-31, a comparison is made between data belonging to the same GLAD. At this time, because the data inside the GLAD is not ordered, the comparison is also performed when the input data dominates the skyline candidate according to lines 29-31. However, if dominance does not occur, and it is also not the same GLAD, the dominance test can be skipped according to Lemma 5 as shown in lines 32 and 33.