earticle

영어

Partitioning of a large scale graph based on traditional graph partitioning algorithm is very effective in improving the performance of application processing on Hadoop. Due to the cost of partitioning, this method drastically reduces the performance benefit. In this paper, we propose a graph partitioning technique using semi-clustering to reduce the cost of graph partitioning and enhance the performance benefit. We also show that our partitioning technique is effective in computing PageRank of a web graph created from Wikipedia. Proposed partitioning technique surpasses the cost of semi-clustering and improves the performance of PageRank computation by more than 15 % on Hadoop cluster.

한국어

Hadoop을 이용하여 대규모 그래프를 처리할 때, 전통적인 그래프 분할 알고리즘에 의한 대규모 그래프의 분할은 성능 개선에 효과적이지만, 분할 알고리즘의 실행 비용은 성능 개선으로 인한 이익을 상당히 감소시킨다. 본 논문에서는 대규모 그래프의 분할 비용을 줄이면서 성능 개선 효과를 높이기 위한 그래프 분할 기법으로, 준클러스터링에 의한 간선 분할 기법을 제안한다. 아울러, 위키피디아로부터 생성된 웹 그래프와 PageRank 알고리즘를 이용하여 그래프 분할 기법의 성능 개선 효과를 분석한다. 준클러스터링에 의한 분할 기법은 Hadoop 클러스터에서 그래프 분할 비용을 제하고도 15% 정도의 성능 개선 효과를 나타내고 있다.