# HI-Sky: Hash Index-Based Skyline Query Processing
## 3 Hash Index-Based Skyline Query Processing
### Hash Index-Based Skyline Query Processing
#### 3.2.1 Background  
Most operations in skyline computation perform dominance tests to determine the dominance among the data. As mentioned in Section 1, domination means that a data point is better than other data points in at least one dimension while being equal to or better than other data points in the remaining dimensions. Here, the criterion for determining a good value is \"\(<\)\" or \"\(>\),\" and in this paper, smaller values are considered better for the consistency of contents. The definition is as follows:  
**Definition 1**. : _Dominance [101]. Given \(d\)-dimensional space \(S=\{s_{1},\,s_{2},\,\dots,\,s_{d}\}\) and data points \(p\) and \(p^{\prime}\) in this space, \(p\) is said to dominate \(p^{\prime}\) if \(\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}]\), and is not said to do so otherwise._  
HI-Sky performs most operations in the dominance test similarly to existing skyline methods. Therefore, for a quick computation of the skyline, it is necessary to remove unnecessary data with minimal comparison. GLAD as used by HI-Sky has the feature of column-major ordering along with the location information of the data space, which has the following characteristics in the skyline:  
**Lemma 1**. : _Given \(d\)-dimensional space \(S=\{s_{1},\,s_{2},\,\dots,\,s_{d}\}\) and arbitrary GLADs a and b composed from a combination of the sequential order of each dimension \(O_{k}\;(k=1\dots d)\), if \(a.O_{k}<b.O_{k}\) in all dimensions that constitute the GLADs, all data that belong to a dominates all data belonging to \(b\)._  
Proof. : A GLAD is formed by a combination of the order of regions divided by the partition in each dimension. Therefore, when the comparison operation is performed on the GLADs, \(O_{k}\;(k=1\dots d)\) orders can be obtained in each dimension. In this case, if arbitrary GLADs \(a\) and \(b\) satisfy \(a.O_{k}<b.O_{k}\) in all dimensions, the data belonging to GLAD \(a\) have a better value in all dimensions than those belonging to GLAD \(b\). Thus, Definition 1 is always satisfied. Figure 2: The partition results and the GLAD assigned to each partition. Lemma 1 shows that HI-Sky can prune the data space using GLAD and can remove a large amount of data early, which significantly reduces the number of dominance tests. In this case, data space pruning is performed only if the corresponding GLAD has a smaller order in all dimensions. This is because, as shown in Figure 2, data point \(A\) may dominate data points such as \(C\) and \(D\) which have the same order in a certain dimension. However, data point \(B\) may not dominate other data points \(C\) and \(D\). As these data do not satisfy the conditions of Lemma 1, i.e., neither point is in a partition with smaller corresponding dimensions than the other point given the order of the partition, data space pruning is not performed. Moreover, even if Lemma 1 is not satisfied, the characteristics of the column-major order in GLAD lead to the following characteristics of Lemma 2 and 3 that can be used to evaluate the need for dominance tests between partitions, and this results in the effective reduction of unnecessary dominance tests:  
**Lemma 2**. : _Given arbitrary GLADs \(a\) and \(b\), if \(a<b\), \(a\) has a smaller value in at least one dimension in which its order is less than that of \(b\)._  
Proof. : GLAD is characterized by a column-major order. Therefore, when each of \(d\)-dimensions is divided into np partitions, the order \(O_{k}\)\((k=1\ldots d)\) of each dimension satisfies \(O_{k}\in[0,\) np\(-1]\), whereas the GLAD is obtained through the following formula:  
\[(\ldots((((O_{1}\times\text{np})+O_{2})\times\text{np})+O_{3})\times\text{np }\ldots)\times\text{np}+O_{d}=\sum_{k=1}^{d}\text{np}^{d-k}\times O_{k} \tag{2}\]  
Therefore, if the condition \(a<b\) is satisfied, \(a\) has at least one dimension smaller than \(b\) from \(O_{1}\) to a specific \(O_{k}\).