그리디 알고리즘을 이용한 맵리듀스 세타조인 M-Bucket-I 휴리스틱의 개선 (Using a Greedy Algorithm for the Improvement of a MapReduce, Theta join, M-Bucket-I Heuristic)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 / 43권 / 2호 / 229 ~ 236페이지
· 저자명 : 김우열, 심규석

초록

세타조인은 데이터베이스에 있어서 가장 기본적이면서도 중요한 질의 중 하나이다. 최근 처리해야 하는 데이터의 양이 증가함에 따라, 맵리듀스와 같은 분산 병렬 처리 프레임워크를 사용한 데이터베이스의 질의처리가 많이 연구되고 있다. 대표적인 연구로 M-Bucket-I 휴리스틱을 이용한 세타조인이 있으나, 이 알고리즘은 수행시간이 입력 데이터의 크기를 이라 할 때, 각 레코드를  max개의 리듀서 중 어느 리듀서로 보낼지 정하는 리듀서맵핑을 구하는데    의 시간이 걸려 쉽게 사용할 수 없다는 문제가있다. 본 논문에서는 기존의 M-Bucket-I 휴리스틱을 개선하여, 같은 리듀서 매핑 결과를 내놓더라도 수행시간이   maxlog  으로 보다 짧은 새로운 알고리즘을 제시한다. 다양한 실험을 통하여 기존의 맵리듀스를 이용한 세타조인보다 성능을 10% 정도 향상시킬 수 있음을 보였다.

영어초록

Theta join is one of the essential and important types of queries in database systems.
As the amount of data needs to be processed increases, processing theta joins with a single machine becomes impractical. Therefore, theta join algorithms using distributed computing frameworks have been studied widely. Although one of the state-of-the-art theta-join algorithms uses M-Bucket-I heuristic, it is hard to use since running time of M-Bucket-I heuristic, which computes a mapping from a record to a reducer (i.e., reducer mapping), is    where  is the size of input data. In this paper, we propose MBI-I algorithm which reduces the running time of M-Bucket-I heuristic to   maxlog   and gives the same result as M-Bucket-I heuristic does. We also conducted several experiments to show algorithm and confirmed that our algorithm can improve the performance of a theta join by 10%.

참고자료

· 없음