# HI-Sky: Hash Index-Based Skyline Query Processing
## 4 Performance Evaluation
### Result of Experiments
#### 4.2.4 Comparison of a Number Dominance Test  
The fourth experiment measured the number of dominance tests in the skyline query. Using these experiments, we compared the performance of the methods through common dominance test calls that have a direct impact on performance for various skyline query methods and therefore have an absolute criterion for query processing time. Finally, we experimented by varying the dimensionality and data distributions to compare various scenarios.  
Figure 8: Skyline computation time according to dimensionality (1 Million).  
Figure 10 shows the results of the number of dominance test calls for each dimensionality and data distribution on the log scale. The experimental results show that SFS and HI-Sky featured fewer dominance test calls than the other methods. These results show that dominance test calls in the MBR, bucket, and RZ-region were not few and, as the number of dimensions increased, the sparsity of the data increased to such an extent that they were not easily dominated. Therefore, an increase in the number of dimensions led to more dominance test calls. Conversely, in the case of SFS, a dominance test between the skyline and actual data was conducted immediately, and thus there was no need for unnecessary comparisons as in the case of dominance tests between MBRs. This was also true for the case of dominance test calls.  
Figure 9: Skyline computation time according to cardinality.  
HI-Sky. However, as HI-Sky removed data that could not be skylines through data space pruning, it operated with fewer data and made fewer calls than the SFS. Moreover, when data were incomparable due to the use of GLAD, dominance test was not performed, which drastically reduced the number of calls. In particular, the efficiency of incomparability is prominently shown in Figure 10e,f, which show the experimental results using anti-correlated data. Anti-correlated data are characterized by a higher number of skylines than other types of data, and also have smaller data spaces or number of actual data points that each skyline can dominate. Therefore, if anti-correlated data are used, the SFS, BBS-R, and BBS-Q make more dominance calls. Meanwhile, Z-SKY can calculate dominance by using the dominance relation of the RZ-region, whereas HI-Sky can determine dominance by using GLAD. Therefore, they conducted fewer dominance tests only when the given data could be dominated, so fewer calls were made than in other methods.  
Figure 10: The number of dominance tests according to dimensionality (1 Million).  
Figure 11 shows the results of the number of dominance test calls for each cardinality and distribution on the log scale using an eight-dimensional dataset. The experimental results show that the number of dominance test calls increases as the cardinality increases. However, BBS-R and BBS-Q showed a higher rate of increase than other methods. This is because the number of nodes increases with the increase of data, and it implies more comparisons for the skyline computation. In case of Z-SKY, unlike the previous method, there is relatively little increase because it is a structure that does not cause node overlap and unnecessary node creation as in R-tree and quadtree. On the other hand, SFS or HI-Sky responds less sensitively to changes in cardinality because the structure, such as the height of the tree and the number of nodes, does not change even if the data increases.  
Figure 11: The number of dominance tests according to cardinality.  
Finally, as described above, because HI-Sky eliminated unnecessary dominance tests by data space pruning and by Lemma 5, it performs skyline computation with the smallest number of dominance tests in most scenarios.