# HI-Sky: Hash Index-Based Skyline Query Processing
## 3 Hash Index-Based Skyline Query Processing
### Hash Index-Based Skyline Query Processing
#### 3.2.2 Data Space Pruning Step  
HI-Sky conducts a two-step skyline computation to maximize the features of Lemmas 1-3. In the first step, the data space is pruned using the features of Lemma 1 to remove the partitioned region where the skyline cannot occur. To this end, we create a window in main memory to store the GLAD (simply GLAD_window) that is not dominated, and prune the data space through a comparison between the GLAD stored in GLAD_window and the next GLAD in sequence. As the GLAD is stored in an ordered manner at the final HashGrid, the characteristic of monotonic ordering is obtained when the GLAD is used sequentially. Therefore, it is unnecessary to check whether the given GLADdominates GLADs stored in GLAD_window, thereby enabling a more efficient computation. The proof of this is in Lemma 4.  
When the data space is pruned using ordered GLADs, the order of the GLADs is characterized by monotonic ordering.  
When ordered GLADs are used in sequence, GLADs stored in GLAD_window are always smaller than the next GLAD in the sequence to be compared. As demonstrated in Lemmas 2 and 3, large GLADs cannot dominate small GLADs. The number of GLADs stored in memory always increases monotonically. Therefore, GLADs are characterized by monotonic ordering.  
Once the first step completes data space pruning for GLADs that cannot contain the skyline, GLADs stored in GLAD_window are used to start the second step of computation for the actual skyline. For an effective skyline computation, a comparison operation is needed between the previously stored GLAD and the given GLAD because a dominance test can only proceed between data if domination can occur. This comparison operation is performed via a general dominance test using Definition 1 when the given GLAD is dominated by one previously stored in GLAD_window. This means that even though the order of some dimensions is the same, data belonging to the preceding GLAD may have a smaller value than those belonging to the given GLAD. However, as demonstrated by Lemma 3, the data in the next GLAD in sequence cannot dominate those in the preceding GLAD; thus, a dominance test is not necessary. Further, these comparisons can be processed more efficiently as a result of Lemma 5.  
When GLADs are ordered and GLAD a and b are given, if a \(<b\) and if a\(.O_{k}>b.O_{k}\) is satisfied in the \(k\)-th dimension \((k=1\ \ldots\ d)\), then b is not dominated by GLAD a, and b cannot be dominated by any subsequent GLAD with identical dimensional order until reaching a GLAD with its last order in the \(k\)-th dimension.  
When ordered GLADs are used and current GLAD b is not dominated by GLAD a due to the order of the \(k\)-th dimension obtained by decomposing GLAD, then there is no need to perform a comparison until reaching a specific GLAD which has the same order in all dimensions except \(k\)-th dimension and has the last order in the \(k\)-th dimension, compared to a. Because GLAD b has a smaller order than the others in the \(k\)-th dimension, Lemma 1 is not satisfied. Therefore, there is no need to perform a comparison because dominance cannot occur, and we can skip the comparison from the current GLAD to the specified GLAD using Lemma 5.