효율적인 맵리듀스 기반 문자열 유사도 조인

Abstract

문자열 유사도 조인은 데이터 베이스 분야에서 매우 중요하고 자주 사용되는 질의이다. 최근 토큰 기반 유사도와 문자 기반 유사도의 장점을 혼합한 Fuzzy 토큰 자카드 유사도가 제안되었다. 그러나 Fuzzy 토큰 자카드 유사도를 이용한 조인은 수행 시간이 너무 오래 걸려 이를 대용량 데이터에서도 사용하기는 어려웠다. 따라서 이를 극복하기 위해 맵리듀스 프레임워크를 이용하는 새로운 분산병렬처리 알고리즘과 이를 위한 새로운 시그니쳐를 제안하였다. 그리고 기존의 단일 머신 알고리즘과 실험을 통해 그 성능을 비교하였으며 20대의 컴퓨터를 이용하였을 때 최대 7배까지 성능이 향상되는 것을 확인할 수 있었다. 또한 컴퓨터의 수를 늘렸을 때 분산처리 방식의 유사도 조인 알고리즘 수행시간이 효과적으로 줄어드는 것을 확인하였다.