Correct Linear Skyline Algorithm in High-Dimensional Space

Heesoo Park, Jongwuk Lee

http://doi.org/10.5626/JOK.2018.45.10.1089

Skyline query is a preference query that finds a candidate set for user preferences, employing the dominance property. It can be effectively used for decision problems that have multiple data attributes. However, a problem arises whereby the skyline becomes too large as the number of attributes in the data increases. To solve this problem, in this paper, we propose a new algorithm for a linear skyline query that restricts a user’s preference function by a linear function. In the previous work, a method was proposed to obtain a linear skyline by adding the same number of virtual points to the data as the number of attributes. However, it has been observed that this previous method does not guarantee the correctness of the linear skyline. We revised this method by adding virtual points in order to find the correct linear skyline. We prove that the proposed algorithm finds the correct linear skyline, and we empirically evaluate the correctness of the proposed algorithm.