Skyline queries are useful for finding only interesting tuples from multi-dimensional datasets for multi-criteria decision making. To improve the performance of skyline query processing for large scale data, it is necessary to use parallel and distributed frameworks such as MapReduce that has been widely used recently. In this dissertation, we propose an efficient method to process skyline queries in a distributed and parallel manner using MapReduce. There are several approaches which process skyline queries on a MapReduce framework to improve the performance of query processing. Some methods process a part of the skyline computation in a serial manner while there are other methods that process all parts of the skyline computation in parallel. However, each of them suffers from at least one of two drawbacks: (1) The serial computations may prevent them from fully utilizing the parallelism of the MapReduce framework; (2) When processing the skyline queries in a parallel and distributed manner, the additional overhead for the parallel processing may outweigh the benefit gained from parallelization. In order to efficiently process skyline queries for large data in parallel, we propose a novel two-phase approach called SKY-IOC in MapReduce framework. In the first phase, we start by dividing the input dataset into a number of subsets (called cells) and then we compute local skylines only for the qualified cells. The outer-cell filter used in this phase considerably improves the performance by eliminating a large number of tuples in unqualified cells. In the second phase, the global skyline is computed from local skylines. To separately determine global skyline tuples from each local skyline in parallel, we design the inner-cell filter and also propose efficient methods to reduce the overhead caused by computing and utilizing the inner-cell filters. The primary advantage of our approach is that it processes skyline queries fast and in a fully parallelized manner in all states of the MapReduce framework with the two filtering techniques. Throughout extensive experiments, we demonstrate that the proposed approach substantially increases the overall performance of skyline queries in comparison with the state-of-the-art skyline processing methods. Especially, the proposed method achieves remarkably good performance and scalability with regard to the dataset size and the dimensionality. Our approach has significant benefits for large-scale query processing of skylines in distributed and parallel computing environments.
스카이라인 질의는 다차원 데이터 집합에서 관심 있는 튜플만을 찾을 수 있어 다기준 의사결정이 필요한 다양한 응용에서 자주 활용된다. 최근 스카이라인 질의가 처리하는 데이터의 규모가 급격하게 커짐에 따라 맵리듀스(MapReduce)와 같은 분산 병렬 프레임웍의 사용이 필요해지고 있다. 본 논문에서는 대표적인 분산 병렬 프레임웍인 맵리듀스를 이용한 효율적인 스카이라인 질의 처리에 대해 논한다. 현재까지 스카이라인 질의 처리 성능을 향상시키기 위해 맵리듀스 프레임웍을 이용한 다양한 방법들이 제안되어 왔다. 이 방법들은 크게 스카이라인 처리 단계의 일부분을 병렬로 처리하는 방법들과 스카이라인 질의 처리 단계의 모든 부분을 병렬로 처리하는 방법들로 나눌 수 있다. 하지만, 이들 각각의 방법들은 다음 두 가지 단점 중 적어도 하나를 가지고 있다. (1) 스카이라인 처리 단계 중 병렬적으로 처리되지 않는 단계로 인해 맵리듀스 프레임웍이 제공하는 병렬처리 능력을 완전히 활용하지 못할 수 있다; (2) 스카이라인 질의 처리를 분산 병렬화하는 과정에서 발생하는 오버헤드(overhead)가 분산 병렬 처리로 얻는 이득보다 클 수 있다. 우리는 대규모 데이터에 대한 스카이라인 질의를 효율적으로 분산 병렬 처리하기 위해 맵리듀스에 기반을 둔 SKY-IOC라는 새로운 2-단계(two-phase) 접근 방식을 제안한다. SKY-IOC의 첫 번째 단계에서는 입력 데이터 집합을 여러 하위 집합(셀이라고 부름)으로 나눈 뒤, 자격이 있는 셀들에 대해서만 로컬 스카이라인들을 계산한다. 이 단계에서 사용되는 외부-셀 필터(outer-cell filter) 는 자격이 없는 셀들에서 모든 튜플을 제거하여 성능을 크게 향상시킨다. SKY-IOC의 두 번째 단계에서는 로컬 스카이라인들로부터 글로벌 스카이라인을 계산한다. 이 단계에서 사용되는 내부-셀 필터(inner-cell filter)는 개별 로컬 스카이라인에서 글로벌 스카이라인 튜플을 병렬로 결정할 수 있게 한다. 또한, 우리는 내부-셀 필터의 계산 및 활용에 수반되는 오버헤드를 줄이기 위한 효과적인 방법들도 함께 제안한다. 제안한 방법의 가장 큰 장점은 외부-셀 필터와 내부-셀 필터를 활용한 두 가지 필터링 기술을 사용하여 맵리듀스의 모든 단계에서 스카이라인 질의를 완벽하게 분산 병렬 방식으로 처리하면서도 분산 병렬화로 인한 오버헤드를 최소화 했다는 점이다. 폭넓은 실험은 제안한 방법이 최신의 기존 방법들보다 스카이라인 질의의 전반적인 처리 성능을 크게 향상 시킨다는 것을 입증한다. 특히, 제안한 방법은 데이터의 크기와 차원수(dimensionality) 에 대하여 현저하게 우수한 성능과 확장성(scalability)을 보인다. 또한, 제안한 방법은 분산 병렬 컴퓨팅 환경에서 대규모 데이터에 대한 스카이라인 질의 처리시 상당한 이점을 가진다.
