# 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  
In this section, we provide a step-by-step explanation of how HI-Sky handles skyline queries. HI-Sky involves a first step of data space pruning using HashGrid and the GLAD stored therein, as described in the previous section. The second step of computing the skyline using data involves the non-pruned GLAD. For HI-Sky, when two-dimensional (2-D) data are given as shown in Figure 1a, they are represented in a 2-D space as shown in Figure 3a. For effective skyline query processing, HI-Sky generates a HashGrid through a hash function that allows grid partitioning using the given data before a skyline query is requested. In this case, if the np used by the hash function is 4, 16 GLADs can be stored in HashGrid in total, from zero (0000) to 15 (1111), as in Figure 3b. They have the property of column-major order due to the combination of bits. Once the HashGrid is completed, only the GLAD that has data as in Figure 3a is stored as the final HashGrid like Figure 3b; if the skyline query is requested, the stored HashGrid is used for it. When a skyline query is requested, the first step of HI-Sky compares the GLAD stored in the HashGrid for data space pruning. At this time, to store the non-pruned data space, a GLAD_window is created and the data spaces shown in dotted lines in Figure 3c are pruned. More specifically, as the order of comparison is in accordance with that of GLAD values, 5 (0101), which is the smallest GLAD of HashGrid, is used first for comparison. This compares the GLAD stored in the GLAD_window with the given GLAD read from the HashGrid based on Lemma 1; if Lemma 1 is not satisfied, it is repeatedly compared with subsequent GLADs stored in the GLAD_window. Initially, 5 (0101) is stored in GLAD_window because GLAD_window is empty, and no regions can be pruned using 5 (0101) through Lemma 3. Then, 7 (0111), 8 (1000), and 9 (1001) are compared in order, and are all stored in the  
Figure 3: An example of skyline query processing based on HI-Sky. (**a**) 2-D data space;(**b**) result of HashGrid; (**c**) data space pruning; (**d**) data pace pruning (cont. ); (**e**) skyline computation; (**f**) skyline computation (cont. ); (**g**) skyline computation (cont. ); (**h**) skyline computation (cont. ); (**i**) result of skyline query  
GLAD_window because no GLAD that can prune them is present in GLAD_window. However, in case of 10 (1010), 11 (1011), 14 (1110), and 15 (1111) (excluding 12 (1100) with data point \(H\)), they are not stored in GLAD_window because we can know that all data in these GLADs are dominated by all data in 5 (0101) according to Lemma 1. Therefore, GLAD_window stores only 5 (0101), 7 (0111), 8 (1000), 9 (1001), and 12 (1100), where the skyline is expected to occur as shown in Figure 3d after the completion of Step 1. Following data space pruning for all GLADs stored in HashGrid, HI-Sky begins the second step, where it computes for the skyline using data from non-pruned GLADs. In this step, the GLAD stored in the GLAD_window is sequentially visited, and the skyline is computed using the data stored in each GLAD. The entropy score minimizes unnecessary comparisons as demonstrated in Lemma 6, and it also monotonically orders the data to enable an efficient skyline computation. Thus, for each piece of data, the entropy score is immediately calculated once the reading is complete. Following entropy score calculation, HI-Sky checks the given GLAD and the GLADs already stored in the Sky_window to determine whether the data belonging to the given GLAD can be dominated by GLADs in the Sky_window. This check is confirmed according to Definition 1 rather than according to Lemma 1 used in data space pruning. If the given GLAD is dominated by the GLAD in Sky_window, there is a possibility of it being dominated by the skyline candidates belonging to the GLAD held in Sky_window, and the skyline candidates stored in the corresponding GLAD and those resulting from the Lemma 6-based comparison are used to confirm dominance.