# HI-Sky: Hash Index-Based Skyline Query Processing
## 1 Introduction  
The skyline query [1] returns data points that are not dominated by other data points in a given database. We refer to such data points as skylines, and domination indicates 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. Figure 1 demonstrates an example of a skyline query. Here, Figure 0(a) lists a given dataset, and Figure 0(b) identifies the skylines of the dataset (i.e., A, G, H). Generally, the skyline query can be used in many real-world applications, such as retail [2], road networks [3], and Web services [4]. Among these, it is commonly known that retail applications deal with dynamic datasets. For example, recently, it was reported that Walmart has high-volume data (i.e., four petabyte) that contains purchase records, where the skyline is frequently used to obtain a set of non-dominant data [5]. Considering that in such retail applications, data points change frequently (i.e., the addition of new purchase records, deletion of the records, or updates on the field values), it is essential to have a skyline query technique that scales well in the presence of the intense amount of updates. In addition, when the dimensionality or quantity of the data points is increased, naive skyline queries lead to degradation in overall performance owing to the higher cost of pairwise data comparisons [1]. This degradation is the result of a significantly increased frequency of the comparison operations needed for performing dominance tests. Thus, to efficiently compute the skylines among alarge amount of high-dimensional data, a more efficient method is required to improve performance relative to existing methods. Among recent proposals, research interest has tended toward index structure-based methods due to their efficiency in handling large amounts of data. These methods generate indices on data for efficient skyline computation when a query is requested. The branch-and-bound skyline (BBS) is a method proposed by [PERSON] et al. [6, 7] that utilizes the features of the R-tree [8, 9]. Z-SKX, proposed by [PERSON] et al. [10, 11], computes the skyline through a ZBtree by combining the B+-tree with a Z-order curve [12, 13]. However, BBS and Z-SKY are not suitable for skyline computation when the data frequently changes, as these methods require a large number of resources to maintain the indices [14, 15]. Moreover, these methods fail to overcome issues related to high-volume data and dimensionality, which greatly influence the performance of indices. In this paper, we propose a hash index-based skyline (HI-Sky), which is a skyline query method based on the hash index. HI-Sky can efficiently create and maintain index structures for large and high-dimensional data, and can eliminate unnecessary pairwise data comparisons when computing the skylines. More precisely, we make the following contributions in this paper:  
* We propose an index structure, which is a fusion of the hash index and grid partitioning (simply HashGrid). HashGrid manages data by grid location address (GLAD), which is a special form of the hash key. We assign GLAD to each grid-partitioned region and perform a region-wise data comparison. This enables us to prune the data space without access to the entire dataset. * We propose a hash index-based skyline (HI-Sky), which is a skyline query method that utilizes the features of HashGrid. HI-Sky computes the skyline through HashGrid using data that only belong to regions not dominated by other GLADs, which is therefore predicted to contain the skyline. This feature allows HI-Sky to avoid accessing unnecessary data that cannot be a skyline and simultaneously performs the dominance test using GLAD to enable efficient computation of the skyline only when domination is possible. * We demonstrate the superiority of HI-Sky through various experiments.