Hadoop 기반의 그래프 분석을 위한 간선 분할 기법
Edge partitioning technique for graph analysis on Hadoop
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
Hadoop을 이용하여 대규모 그래프를 처리할 때, 전통적인 그래프 분할 알고리즘에 의한 대규모 그래프의 분할은 성능 개선에 효과적이지만, 분할 알고리즘의 실행 비용은 성능 개선으로 인한 이익을 상당히 감소시킨다. 본 논문에서는 대규모 그래프의 분할 비용을 줄이면서 성능 개선 효과를 높이기 위한 그래프 분할 기법으로, 준클러스터링에 의한 간선 분할 기법을 제안한다. 아울러, 위키피디아로부터 생성된 웹 그래프와 PageRank 알고리즘를 이용하여 그래프 분할 기법의 성능 개선 효과를 분석한다. 준클러스터링에 의한 분할 기법은 Hadoop 클러스터에서 그래프 분할 비용을 제하고도 15% 정도의 성능 개선 효과를 나타내고 있다.
Abstract
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.
참고문헌 (23)
- 이종근, "클라우드 컴퓨팅을 이용한 개인 유전체 정보 분석: 병렬 CNV 영역 검색 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(3), pp.4~11 (2010), 한국차세대컴퓨팅학회
- Naveed Ejaz, "Efficient Soical Network Data Analysis by Utilizing Cloud Computing Infrastructure", 한국차세대컴퓨팅학회 논문지, 8(3), pp.47~56 (2012), 한국차세대컴퓨팅학회[DOI]
- 이강윤, "서비스 사이언스에 기반한 클라우드 컴퓨팅 서비스 모델 연구", 한국차세대컴퓨팅학회 논문지, 6(1), pp.50~57 (2010), 한국차세대컴퓨팅학회
- J. Dean, "MapReduce: simplified data processing on large clusters" (2004), OSDI
- G. Malewicz, "Pregel: a system for large-scale graph processing" (2010), SIGMOD
- A. Shinnar, "M3R: Increased performance for in-memory Hadoop jobs" (2012), VLDB
- "Hadoop"[URL]
- J. Lin, "Design pattern for efficient graph algorithms in MapReduce" (2010), MLG
- J. Huang, "Scalable SPARQL querying of large RDF graphs" (2011), VLDB
- J. Cohen, "Graph twiddling in a MapReduce world", Computingin Science and Engineering (2009)
- D. Chakrabarti, "Graph mining: Laws, generators, and algorithms", ACM Computing Survey, 38 (2006)
- Y. Bu, "HaLoop: Efficient iterative data processing on large clusters" (2010), VLDB
- "Giraph"[URL]
- GPS: A graph processing system, "S. Salihoglu", Stanford InfoLab, ~ (2012)
- The PageRank citation ranking: bringingorder to the web, "L. Page", StanfordInfoLab, ~ (1999)
- 김태원, "웹 페이지 컨텐츠 점수를 이용한 개선된 페이지랭크 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(3), pp.12~19 (2010), 한국차세대컴퓨팅학회
- K. Avrachenkov, "PageRank based clustering of hypertext document collections" (2008), SIGIR
- S. White, "Algorithms for estimating relative importance in networks" (2003), KDD
- G. Ivn, "When the web meets the cell: Using personalized PageRank for analyzing protein interaction networks", Bioinformatics Advance Access (2010)
- J. Kleinberg, "Authoritative sources in a hyperlinked environment", JACM, 46(5), pp.604~632 (1999)
- H. Lee, "Perturbation of the hyperlinked environment" (2003), COCOON
- "Wikipedia data set"[URL]
- "Joycrawler"[URL]