Earticle

초록

한국어

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

영어

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.

목차

요약
 Abstract
 1. 서론
 2. 관련연구
  2.1 그래프 병렬 처리 모델
  2.2 Hadoop의 그래프 분할 기법
  2.3 페이지랭크 알고리즘
 3. 준클러스터링에 의한 그래프의 간선 분할
  3.1 정점의 외향 차수 계산
  3.2 준클러스터의 생성
  3.3 데이터 파티션에 준클러스터의 할당
 4. 성능 평가
  4.1 실험 환경
  4.2 준클러스터링에 의한 PageRank의 성능 개선 효과
  4.3 메모리 크기가 페이지 랭크 실행 시간에 미치는 영향
 5. 결론
 참고문헌

저자

• 최동훈 [ Dong Hoon Choi | 한국과학기술정보연구원 정보소프트웨어센터 ]
• 엄정호 [ Jung-Ho Um | 한국과학기술정보연구원 정보소프트웨어센터 ] 교신저자
• 윤화묵 [ Hwa Mook Yoon | 한국과학기술정보연구원 정보소프트웨어센터 ]
• 최윤수 [ Yun-Soo Choi | 한국과학기술정보연구원 정보소프트웨어센터 ]
• 이민호 [ Min Ho Lee | 한국과학기술정보연구원 정보소프트웨어센터 ]
• 이원구 [ Won-Goo Lee | 한국과학기술정보연구원 정보소프트웨어센터 ]
• 송사광 [ Sa-kwang Song | 한국과학기술정보연구원 정보소프트웨어센터 ]
• 정한민 [ Hanmin Jung | 한국과학기술정보연구원 정보소프트웨어센터 ]
• 이명호 [ Myungho Lee | 명지대학교 컴퓨터공학과 ]

참고문헌