Hadoop 기반의 그래프 분석을 위한 간선 분할 기법 = Edge partitioning technique for graph analysis on Hadoop

국문 초록 (Abstract)

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

목차 (Table of Contents)

• 요약
• 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. 결론
• 참고문헌

참고문헌 (Reference)

1 이종근, "클라우드 컴퓨팅을 이용한 개인 유전체 정보 분석: 병렬 CNV 영역 검색 알고리즘" 한국차세대컴퓨팅학회 6 (6): 4-11, 2010

2 김태원, "웹 페이지 컨텐츠 점수를 이용한 개선된 페이지랭크 알고리즘" 한국차세대컴퓨팅학회 6 (6): 12-19, 2010

3 이강윤, "서비스 사이언스에 기반한 클라우드 컴퓨팅 서비스 모델 연구" 한국차세대컴퓨팅학회 6 (6): 50-57, 2010

4 "Wikipedia data set"

5 G. Ivn, "When the web meets the cell: Using personalized PageRank for analyzing protein interaction networks" 2010

6 L. Page, "The PageRank citation ranking: bringingorder to the web" StanfordInfoLab 1999

7 J. Huang, "Scalable SPARQL querying of large RDF graphs" VLDB 2011

8 G. Malewicz, "Pregel: a system for large-scale graph processing" SIGMOD 2010

9 H. Lee, "Perturbation of the hyperlinked environment" COCOON 2003

10 K. Avrachenkov, "PageRank based clustering of hypertext document collections" SIGIR 2008

11 J. Dean, "MapReduce: simplified data processing on large clusters" OSDI 2004

12 A. Shinnar, "M3R: Increased performance for in-memory Hadoop jobs" VLDB 2012

13 "Joycrawler"

14 "Hadoop"

15 Y. Bu, "HaLoop: Efficient iterative data processing on large clusters" VLDB 2010

16 J. Cohen, "Graph twiddling in a MapReduce world" 2009

17 D. Chakrabarti, "Graph mining: Laws, generators, and algorithms" 38 : 2006

18 "Giraph"

19 S. Salihoglu, "GPS: A graph processing system" Stanford InfoLab 2012

20 Naveed Ejaz, "Efficient Soical Network Data Analysis by Utilizing Cloud Computing Infrastructure" 한국차세대컴퓨팅학회 8 (8): 47-56, 2012

21 J. Lin, "Design pattern for efficient graph algorithms in MapReduce" MLG 2010

22 J. Kleinberg, "Authoritative sources in a hyperlinked environment" 46 (46): 604-632, 1999

23 S. White, "Algorithms for estimating relative importance in networks" KDD 2003