상용 클러스터로 대규모 그래프의 연결 요소를 계산하기 위한 효율적인 알고리즘
An Efficient Algorithm for Computing Connected Components of an Enormous Graph using a Commodity Cluster
- 주제(키워드) 연결 요소 , 그래프 알고리즘 , 분산 알고리즘 , 맵리듀스 , Connected components , Graph algorithm , Distributed algorithm , MapReduce
- 발행기관 국민대학교 일반대학원
- 지도교수 박하명
- 발행년도 2021
- 학위수여년월 2022. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과 컴퓨터공학전공
- 원문페이지 v, 35
- 실제URI http://www.dcollection.net/handler/kookmin/200000599573
- UCI I804:11014-200000599573
- 본문언어 한국어
초록/요약
최근 웹의 데이터가 폭발적으로 증가함에 따라 상용 클러스터 서버에서 수천억 개의 정점과 간선을 가지는 거대한 그래프에서 연결 요소(Connected Components)를 효율적으로 계산하는 것이 매우 중요한 문제가 되었다. 지금까지 연구된 단일 머신 및 분산 메모리 알고리즘들은 입력 데이터와 처리 과정에서 생성되는 모든 데이터를 주 메모리에 적재하여 실행하기 때문에 확장성이 제한된다. 단일 머신 및 분산 메모리 알고리즘에서 거대한 데이터를 처리하기 위해서는 방대한 메모리가 탑재되어 있는 고가의 머신이 필요하다. 또한 기존에 연구된 맵리듀스 알고리즘들은 분산 파일 시스템을 이용하여 거대한 그래프 처리를 시도하지만 중간 데이터 폭증 문제로 인하여 처리에 실패한다. 최근에 제안된 맵리듀스 알고리즘들은 두 개의 분산 연산으로 이루어진 star-operation을 교대로 실행하여 중간 데이터 폭증 문제를 해결하지만 두 개의 분산 연산을 반복하여 실행하기 때문에 심각한 네트워크 트래픽과 디스크 I/O를 발생시킨다. 본 논문에서는 두 개의 분산 연산으로 이루어진 star-operation을 하나로 통합하는 분산 연산 UniStar를 제안하고, UniStar를 이용하여 거대한 그래프에서 연결 요소를 계산하는 분산 알고리즘 UniCon을 제안한다. UniStar는 파티션 인식 처리 기법을 통해 중간 데이터 폭증 문제를 해결한다. 또한 연산 과정에서 불필요한 간선들을 제거하고, 새로운 하이브리드 자료구조를 이용하여 UniStar 연산을 최적화한다. UniCon은 10대의 저가의 머신으로 이루어진 상용 클러스터 서버에서 실험이 진행되어 실제 그래프 데이터에서 경쟁 알고리즘들보다 최대 13배 빠르게 실행된다. 실험 결과, UniCon은 1,290억 개의 간선을 가지는 거대한 그래프 처리에 성공하여 경쟁 알고리즘들보다 최대 4096배 큰 데이터 처리에 성공한다.
more초록/요약
With a cluster of commodity hardware, how can we efficiently find all connected components of a web-scale graph containing hundreds of billions of nodes and edges? Most existing single-machine and distributed-memory algorithms are limited in scalability as they have to load all data generated during the process into the main memory; they require expensive machines with vast memory capacities to handle large graphs. Several MapReduce algorithms try to handle large graphs by exploiting distributed storage but fail due to data explosion problems. The latest MapReduce algorithms resolve the problem by proposing two distinguishing star-operations and executing them alternately, while the star-operations still cause massive network traffic. In this paper, we unite the two star-operations into a single operation, namely UniStar, and propose UniCon, a new distributed algorithm for finding connected components in web-scale graphs using UniStar. The partition-aware processing of UniStar effectively resolves the data explosion problems. We further optimize UniStar by filtering dispensable edges and exploiting a hybrid data structure. Experimental results with a cluster of 10 cheap machines show that UniCon is up to 13 times faster than competitors on real-world graphs. UniCon succeeds in processing a tremendous graph with 129 billion edges, which is up to 4096 times larger than graphs competitors can process.
more목차
제 1장 서론 1
제 2장 관련 연구 3
2.1 단일 머신 알고리즘 3
2.2 분산 메모리 알고리즘 3
2.3 맵리듀스 알고리즘 4
제 3장 문제 정의 6
제 4장 제안 방법: UniCon 8
4.1 UniCon의 구조 9
4.2 통합된 star-operation: UniStar 10
4.2.1 UniStar-naïve 10
4.2.2 UniStar 11
4.3 불필요한 간선 필터링: UniStar-opt 14
4.4 새로운 하이브리드 자료구조: HybirdMap 17
제 5장 Evaluation 19
5.1 실험 환경 20
5.1.1 실험 데이터 셋 20
5.1.2 하드웨어 20
5.1.3 알고리즘 20
5.1.4 실험 매개변수 21
5.2 UniStar의 효율성 22
5.3 간선 필터링의 효율성 23
5.4 HybridMap의 효율성 25
5.5 확장성 27
5.6 실제 데이터 셋에서의 성능 28
제 6장 결론 30
참고 문헌 31
영문 요약 35