Skyline query filters out a set of interesting points from a large set of data. A point is said to be interesting if it is not dominated by any other point. There has been a growing interest in algorithms for efficiently evaluating skyline queries. However, most of the algorithms require additional data structure in the database server which, in most cases, is not feasible. In this paper we only concentrate in scenarios where additional data structure is not available. Currently, the most efficient algorithm in such circumstance is SaLSa(Sort and Limit Skyline algorithm). SaLSa takes the idea of pre-sorting and limiting the data to compute skyline without having to read the whole data. However, since SaLSa computes the stop point during the progress of the algorithm, the potential of the stop point cannot be fully utilized. In this paper we propose SWT(Skyline with Transformation) which maximizes the potential limiting ability of the stop point, and verify that SWT outperforms SaLSa.
스카이라인 질의는 사용자의 선호도를 고려하여 무수히 많은 데이터로부터 사용자에게 유용한 정보만을 반환한다. 유용한 정보란, 다른 데이터에 의해 지배당하지 않는 데이터로 정의 된다. 스카이라인을 효율적으로 계산하기 위한 많은 방법들이 연구 되었지만, 대부분의 알고리즘은 데이터베이스 서버 내에 별도의 자료구조를 필요로 한다. 하지만 우리가 일반적으로 사용하는 데이터베이스로부터 이러한 조건이 항상 만족되기를 기대할 수는 없다. 본 논문에서는 별도의 자료구조의 사용이 유효하지 않은 상황만을 가정한다. 이와 같은 상황에서 현존하는 최적의 알고리즘으로 Sort and Limit Skyline Algorithm(SaLSa)이 있다. SaLSa는 정렬된 데이터와 정지점의 활용으로 전체 데이터 중 일부만 읽으며 스카이라인을 계산할 수 있다. 하지만 정지점을 중간에 계산하는 SaLSa는 정지점의 기능을 충분히 활용하지 못한다. 본 논문에서는 정지점을 미리 계산하여 정지점의 제거기능을 최대화시킨 효율적인 스카이라인 알고리즘 Skyline with Transformation(SWT)을 제안하고, 실험을 통해 SWT가 SaLSa에 비해 데이터 제거 효과 및 스카이라인 질의 처리 속도가 우수함을 검증한다.
