중복 기반 조인을 이용한 맵리듀스에서의 효율적인 SPARQL 질의 처리 기법

Abstract

최근, 분산 병렬 프레임워크인 맵리듀스를 이용한 SPARQL 질의 처리에 대한 연구가 진행되고 있다. 맵리듀스를 이용해 SPARQL 질의 처리를 하기 위해서는 여러 맵리듀스 잡이 필요하며, 이로 인해 많은 비용이 들게 된다. 최근의 연구들은 대부분 이 맵리듀스 잡의 개수를 줄이는데 초점을 맞추고 있다. 본 논문은 SPARQL 질의 처리시에 맵리듀스 잡의 개수를 줄이기 위한 두 가지 서로 다른 기법을 혼용 할 것을 제안한다. 우리가 적용한 기법은 서로 관련이 없는 조인 키들을 동시에 하나의 맵리듀스 잡에서 수행하는 비상충 조인과 중복을 이용해서 여러 개의 조인 키를 한번에 조인하는 멀티웨이 조인 기법이다. 이 두 가지 기법을 혼용함으로써, 기존에 제안된 기법보다 적은 수의 맵리듀스 잡을 이용해 질의를 처리 할 수 있다. 또한, 이로 인해 발생하는 트리플 패턴 그룹화 문제에 대한 그리디 알고리즘을 제안한다. 우리는 대용량 RDF 데이터를 이용한 실험을 통해 제안하는 알고리즘이 기존 연구보다 맵리듀스 잡의 개수를 줄일 수 있으며, 질의 처리 성능을 향상 시킴을 보인다.

Recently, there has been a lot of research about SPARQL query processing using MapReduce, a parallel distributed framework. To process a SPARQL query on MapReduce, in general, several MapReduce jobs are required, and these jobs cause additional costs. Therefore, most research has been focused on reducing the number of MapReduce jobs. In this paper, we propose to hybridize two different techniques to reduce the number of MapReduce jobs for processing SPARQL query. The techniques we hybridize are the non-conflicting join and the duplication-based multi-way joins. The non-conflicting join can process independent joins in one MapReduce job, and the multi-way joins can join many join keys at once by duplicating data. Also, we present a greedy algorithm to solve the triple pattern grouping problem which occurs when hybridizing two techniques. We demonstrate that our framework can reduce MapRedcue jobs, and performs better than the previous approaches, through experiments on the large RDF data.