# HI-Sky: Hash Index-Based Skyline Query Processing
## 3 Hash Index-Based Skyline Query Processing
### Hash Index for Skyline  
In the past, major index structures have used a tree structure to accomplish data computation with a minimal number of operations. Existing tree structure methods such as the R-tree and B+-tree store data in a cluster under a certain standard. This feature makes it possible to quickly remove large amounts of data without requiring a comparison. Therefore, though conventional methods have the disadvantage of requiring dominance testing on all data, this can be obviated through the index structure to enable the efficient processing of large volumes of data, such as big data. However, tree structure-based approaches based on the R-tree or B+-tree methods, such as BBS and Z-SKY, increase data sparsity in the data space by increasing the absolute distance between data points as the number of dimensions increases. This significantly reduces the probability of data space pruning in the MBR or the RZ-region. Moreover, these methods are expensive to preprocess or traverse for skyline computation. It is also difficult to utilize these methods in environments where data insertion and deletion are frequent because it leads to expensive operations such as changes to the tree structure [27; 28; 29]. In such cases, skyline computation requires a new index structure method capable of clustering the given data and maintaining it at low cost. HashGrid is a fusion of the hash index [30; 31] and grid partitioning [32; 33], and allows for chaining. The most important feature of hash indices is that very little time is needed to find the bucket where data is stored, or will be stored. Chaining-based hash indices are also robust in terms of maintenance because they do not require changes to other buckets when storing or deleting data. Therefore, in generating and maintaining indices using large amounts of data, a hash index can be generated more quickly than a conventional tree-based method, and maintenance cost is thus reduced. Further, hash index clusters similar data points in the same hash bucket, similarly to tree structures. At the same time, it is common to use a formula that can distribute the data as uniformly as possible. Therefore, to effectively use the hash index in skyline computation, it is important to select a hash function that can cluster data based on the data space and sparsity. Moreover, the generated hash key must be able to prune the data space without needing to access the real data. To do this, the hash function used in HashGrid divides the given data at regular intervals in each dimension and combines them sequentially to generate a hash key. Then, the number of partitions (np) for dividing each dimension is input by the user. Alternatively, given the number of dimensions \(d\), the minimum bucket capacity \(C\), and the number of data \(N\), the maximum value of np can be obtained from the following Equation (1). \[\max(np)=\left\{ \begin{array}{cc}\left[\sqrt[d]{N/C}\right],&\sqrt[d]{N/C} \geq 2\\ 2,&\sqrt[d]{N/C}<2\end{array} \right. \tag{1}\]  
Equation (1) computes the maximum value of np required to store the amount of data close to the minimum capacity into the partitioned space, assuming that a uniformly distributed dataset is given. However, it returns 2, the minimum value of np, when there is no value satisfying this criterion. Then, the final np is selected from the minimum value of np (np = 2) to the maximum value of np. Finally, if the data is correlated or anti-correlated, better performance can be obtained by using a value slightly larger than the maximum value of np obtained through Equation (1). The hash key generated using this np represents the position of the grid-partitioned region, which we call GLAD.