데이터 샘플링 기반 프루닝 기법을 도입한 효율적인 각도 기반 공간 분할 병렬 스카이라인 질의 처리 기법 (An Efficient Angular Space Partitioning Based Skyline Query Processing Using Sampling-Based Pruning)

서지정보

· 발행기관 : 한국정보처리학회
· 수록지 정보 : 정보처리학회 논문지 / 6권 / 1호 / 1 ~ 8페이지
· 저자명 : 최우성, 김민석, GROMYKO DIANA, 정재화, 정순영

초록

다기준 의사결정 시 활용할 수 있는 스카이라인 질의는 다수의 선택지 중에서 사용자가 ‘선호하지 않을 만한’(uninteresting) 선택지를 제거함으로써 사용자가 검토해야 하는 선택지의 수를 대폭 감소시키기 때문에 대용량 데이터 분석 시 매우 유용하게 활용될 수 있다. 이러한 배경에서 대용량 데이터에 대한 스카이라인 질의를 분산ㆍ병렬 처리하는 기법이 각광을 받고 있으며, 특히 맵리듀스(MapReduce) 기반의 분산ㆍ병렬 처리 기법 연구가 활발히 진행되어 왔다. 맵리듀스 기반 알고리즘의 병렬성 제고를 위해서는 부하 불균등 문제ㆍ중복 계산 문제ㆍ과다한 네트워크 비용 발생 문제를 해소해야 한다. 본 논문에서는 부하 불균등 문제와 중복 계산 문제를 해소하면서도 데이터 샘플링 기반 프루닝을 통해 네트워크 비용 절감 시킬 수 있는 맵리듀스 기반 병렬 스카이라인 질의 처리 기법인 MR-SEAP(MapReduce sample Skyline object Equality Angular Partitioning)을 소개한다. 또한 다양한 관점에서의 실험 평가함으로써 제안 기법의 효용성을 다방면으로 검증했다.

영어초록

Given a multi-dimensional dataset of tuples, a skyline query returns a subset of tuples which are not ‘dominated’ by any other tuples. Skyline query is very useful in Big data analysis since it filters out uninteresting items. Much interest was devoted to the MapReduce-based parallel processing of skyline queries in large-scale distributed environment. There are three requirements to improve parallelism in MapReduced-based algorithms: (1) workload should be well balanced (2) avoid redundant computations (3) Optimize network communication cost. In this paper, we introduce MR-SEAP(MapReduce sample Skyline object Equality Angular Partitioning), an efficient angular space partitioning based skyline query processing using sampling-based pruning, which satisfies requirements above. We conduct an extensive experiment to evaluate MR-SEAP.

참고자료

· 없음