스카이라인 질의는 여러 분야에서 지속적인 관심을 받고 있으며, 질의의 성능 개선을 위하여 다양한 최적화 기법들이 제안되었다. 이러한 최적화 기법들은 주로 지배 관계 판별 연산을 최소화하기 위하여 피지배객체(non-skyline object)의 제거에 중점을 두고 있다. 하지만, 다차원의 대용량 데이터의 경우, 이러한 최적화 기법들은 충분한 효율을 보이지 못하고 있다. 더욱이 스카이라인 질의는 데이터 집합의 분포의 특성에 따라 처리 비용이 달라지는데 기존 기법들은 이러한 분포를 고려하고 있지 않다. 본 논문에서는 데이터의 상관도를 고려하여 성능을 최적화할 수 있는 기법인 HashSkyline을 제안한다. HashSkyline은 전처리 단계에서 데이터의 분포를 우선 파악하여 많은 비용이 소모되고 의미 없는 스카이라인 연산을 피할 수 있도록 한다.
Skyline queries continue to attract attentions from both research communities and big data application developers since the skyline operator was first proposed in 2001. Different optimization techniques have been developed to improve the performance of skyline queries. However, most of the techniques fail to scale over large datasets in practice. We argue that skyline query optimization should exploit the divide-and-conquer approach in both computation steps and data correlation characteristics. In this paper, we exploit the data correlation to speed up the Skyline computation for correlated datasets. We propose a novel and fast skyline computation approach, called HashSkyline, with two unique features. First, HashSkyline minimizes the pre-processing cost to O(n) by effectively utilizing the characteristics of correlated datasets to explore new optimization opportunities for skyline computation. Second, HashSkyline capitalizes on a hash cell based mechanism to learn the level of correlation among the data points in a given dataset at low processing cost, allowing early detection of anti-correlated datasets at early stage to avoid uninteresting and yet high cost of computing skylines on anti-correlated datasets.
