# HI-Sky: Hash Index-Based Skyline Query Processing
## 4 Performance Evaluation
### Result of Experiments
#### 4.2.3 Comparison of Skyline Computation Time  
The third experiment measured the time required to complete the skyline query to determine the performance of skyline computation. In this case, the SFS required preprocessing to calculate entropy score and perform sorting, and HI-Sky used preprocessing to perform data space pruning. Figure 7: Results of HashGrid maintenance performance on dynamic dataset. Therefore, because the SFS and HI-Sky performed preprocessing, skyline computation time included preprocessing time, whereas because BBS-Q, BBS-R, and Z-SKY did not require preprocessing, only the time required for skyline computation was included. We experimented with dimensionality and cardinality using varying data distributions. Figure 8 shows the results of skyline computation times for each dimension and distribution on the log scale. The experimental results show that the BBS-Q and BBS-R yielded the best performance in the case of independent and correlated data with four dimensions. Because the MBR of the BBS-R and the bucket of the BBS-Q have a hierarchical inclusion relationship, it was possible to remove large amounts of data even with a small number of comparisons. However, in the case of BBS-R, as the number of dimensions increased, the problem of overlapping among the MBRs increased significantly and, owing to a lack of monotonic ordering, the efficiency of the dominance test was low. In the case of BBS-Q, \(2^{d}\) buckets are created for each split, and the creation of child buckets exceeding than the capacity of the bucket results in empty buckets, which reduces the efficiency of the dominance test. Therefore, as the number of dimensions increased, skyline computation in the BBS-R and BBS-Q were drastically affected. However, in the case of the SFS and HI-Sky, as the dominance test was performed effectively by utilizing the characteristics of monotonic ordering, comparatively small changes in performance occurred even when the number of dimensions increased. Meanwhile, in the case of HI-Sky, the dominance test was not performed when dominance did not occur because GLAD was used, which rendered HI-Sky more effective than the SFS. Lastly, Z-SKY is demonstrated only using integers because it depends heavily on the data type and data range due to the Z-Address. Z-SKY demonstrated poor performance in most cases as a result of three identifiable problems. First, the ZBtree has poor performance because of its repeated dominance tests from root to leaf and its performance sensitivity to node capacity. Z-SKY uses the ZBtree to store the skyline in a similar manner to indexing, but this requires costly tree construction and maintenance, as mentioned in the second experiment. Second, Z-SKY performs a dominance test on the RZ-regions of each node. This test is performed every time new data is entered, starting from the root, until it is dominated or selected as skyline. In this process, child nodes of the RZ-region that need to be compared are repeatedly stored in queue and sequential comparison with them is performed in turn. The data selected as the skyline need to be compared with all RZ-regions or candidate skylines in the queue, which often requires more comparisons than performing a comparison using actual data with monotonic ordering. Third, depending on the node's capacity, the height of the ZBtree and the maximum number of child nodes stored in the queue changes, which has a significant effect on overall performance. Therefore, choosing an incorrect capacity can significantly affect the overall performance, and it is difficult to select the optimum capacity in advance. Figure 9 shows the results of skyline computation times for each cardinality and distribution on the log scale using an eight-dimensional dataset. For HI-Sky, to check only the effect due to cardinality, np is set to four, which is that of the default dataset (8 D, 1 M). The experimental results show that the SFS yielded the best performance in the case of independent and correlated data with a 10 K dataset.