# HI-Sky: Hash Index-Based Skyline Query Processing
## 3 Hash Index-Based Skyline Query Processing
### Hash Index-Based Skyline Query Processing
#### 3.2.3 Skyline Computation Step  
After the data space pruning is completed, the skyline computation step is performed to compute the actual skyline using the GLADs in GLAD_window. At that stage, because skyline candidates also need to be managed according to their GLADs, a window for each GLAD (simply Sky_window) is created in main memory, and the selected data are stored in the Sky_window of each GLAD as a skyline candidate. In this process, we can perform the skyline computation step more effectively through the dominance test using GLADs. If the current GLAD is not dominated by a GLAD that was previously stored a skyline candidate in Sky_window, Lemma 5 allows us to skip unnecessary dominance testing between the data in each GLAD. Data that belong to the same GLAD stored in the Sky_window then need to be compared with one another. However, data belonging to the same GLAD are not monotonically ordered, and thus the efficiency of the computation can be drastically reduced if the data are compared in a naive manner. To solve this problem, HI-Sky calculates the entropy score of the data to check for dominance, minimizing the efficiency reduction.  
**Definition 2**.: _Entropy score [16; 17]. Given \(d\)-dimensional space \(S=\{s_{1},\,s_{2},\,\ldots,\,s_{d}\}\) and a data point \(p\) belonging to that space, the entropy score of \(p\), \(E(p)\), is calculated using the actual values of each dimension of \(p\) as follows:_  
\[E(p)\,=\,\sum_{k=1}^{d}\ln(p[s_{k}]+1) \tag{3}\]  
Such an entropy score enables monotonic ordering of the given data. Thus, to dominate specific data points, the given data point must have an entropy score smaller than a specific data point. On the contrary, when the entropy score of the given data point is greater than that of the specific data point, the latter is likely to dominate the former. The proof of this is as follows:  
**Lemma 6**.: _Given \(d\)-dimensional space \(S=\{s_{1},\,s_{2},\,\ldots,\,s_{d}\}\) and data points \(p\) and \(p^{\prime}\) belonging to that space, if the calculated entropy score of both data points satisfies the \(p\) dominates \(p^{\prime}\) relationship, this condition is sufficient to show that \(E(p)<E(p^{\prime})\)._  
Proof.: For \(p\) to dominate \(p^{\prime}\) by Definition 1, it must satisfy \(\forall s_{d}\in S\), \(p[s_{d}]\leq p^{\prime[s_{d}]}\wedge\exists s_{x}\in S\), \(p[s_{x}]<\,p^{\prime[s_{x}]}\). Therefore, to dominate a specific data point, the data point must have values smaller than or equal to that specific data point in all dimensions, with a smaller value in at least one dimension. When this condition is extended to Definition 2, \(E(p)<E(p^{\prime})\) is always satisfied when \(p\) dominates \(p^{\prime}\).  
Using these characteristics, HI-Sky confirms by use of entropy score whether the data point belonging to the same GLAD is dominated by the given data point, or whether the given data point is itself dominated. To perform these operations more efficiently, data that are not dominated are sorted by entropy score and stored in a Sky_window.  
However, the features of Lemma 6 apply equally to dominance tests of all data and data points from the same GLAD. In particular, even if a comparison is made with a skyline candidate belonging to a relatively small GLAD, the given data can be dominated only if Lemma 6 is satisfied. If this is not the case, according to Lemma 3, the dominance test for the relevant GLAD can be completed early because the given data do not dominate the remaining skyline candidates. Therefore, HI-Sky prunes the data space early where the skyline cannot occur through Lemma 1, and compares all skyline candidates that can dominate the given data or can be dominated by them. Thus, HI-Sky computes for the exact number of skyline points.  
In this way, HI-Sky performs fast skyline computation by data space pruning in data space pruning step, through various features of HashGrid, GLAD, and entropy score, and by the removal of most dominance tests in skyline computation step when absolute dominance cannot occur.