정지점의 활용을 극대화한 효율적인 스카이라인 계산법

Abstract

스카이라인 질의는 사용자의 선호도를 고려하여 무수히 많은 데이터로부터 사용자에게 유용한 정보만을 반환한다. 유용한 정보란, 다른 데이터에 의해 지배당하지 않는 데이터로 정의 된다. 스카이라인을 효율적으로 계산하기 위한 많은 방법들이 연구 되었지만, 대부분의 알고리즘은 데이터베이스 서버 내에 별도의 자료구조를 필요로 한다. 하지만 우리가 일반적으로 사용하는 데이터베이스로부터 이러한 조건이 항상 만족되기를 기대할 수는 없다. 본 논문에서는 별도의 자료구조의 사용이 유효하지 않은 상황만을 가정한다. 이와 같은 상황에서 현존하는 최적의 알고리즘으로 Sort and Limit Skyline Algorithm(SaLSa)이 있다. SaLSa는 정렬된 데이터와 정지점의 활용으로 전체 데이터 중 일부만 읽으며 스카이라인을 계산할 수 있다. 하지만 정지점을 중간에 계산하는 SaLSa는 정지점의 기능을 충분히 활용하지 못한다. 본 논문에서는 정지점을 미리 계산하여 정지점의 제거기능을 최대화시킨 효율적인 스카이라인 알고리즘 Skyline with Transformation(SWT)을 제안하고, 실험을 통해 SWT가 SaLSa에 비해 데이터 제거 효과 및 스카이라인 질의 처리 속도가 우수함을 검증한다.