맵리듀스를 사용한 최대흐름 알고리즘의 구현과 사례 연구

• 영문명: Mapreduce-Based Maximum Flow Algorithm: Implementation and Experimental Results
• 발행기관: 한국자료분석학회
• 저자명: 강진아(Jina Kang) 원중호(Joong-Ho Won)
• 간행물 정보: 『Journal of The Korean Data Analysis Society (JKDAS)』Vol.16 No.6, 2999~3012쪽, 전체 14쪽
• 주제분류: 자연과학 > 통계학
• 파일형태: PDF
• 발행일자: 2014.12.30

국문 초록

데이터의 규모가 급속히 증가하고 있는 현 시점에서 이러한 빅 데이터 처리를 위한 분산 컴퓨팅 환경으로 하둡(Hadoop)과 맵리듀스(Mapreduce)가 사실상의 표준으로 떠오르고 있으나, 이 환경에서의 실질적인 데이터 분석을 위한 방법론 개발에 대한 논의는 비교적 적은 편이다. 본 연구는 대표적인 네트워크 데이터 분석 알고리즘인 최대흐름 문제를 맵리듀스 분산 환경에서 처리하는 방법에 대해 소개하고, 맵리듀스를 기반으로 하는 대규모 최대흐름 알고리즘을 파이썬(Python) 언어를 이용하여 구현한 뒤, 하둡 환경에서 수행해보았다. 랜덤 네트워크와 영상 분할 데이터를 이용한 실험을 통해 수행 시간 및 확장성을 측정하였다. 랜덤 네트워크 실험에서는 정점의 수를 1000개부터 100만개까지 사용하였고, 영상 분할 실험에서는 정점의 수를 약 20개부터 크게는 약 17000개까지 사용하여 단일 서버와 분산 서버에서의 수행 시간을 비교하는 실험을 하였다. 이를 통해 맵리듀스 기반 알고리즘의 가능성과 한계에 대해 알아본다.

영문 초록

In this ‘big data’ era, in which the sizes of data sets are ever increasing, while Hadoop and the MapReduce framework are emerging as the de-facto standard for big data analysis, it is seldom discussed how to utilize them and develop algorithms for complex data analysis problems. In this paper, we review the maximum flow problem, an important subject in network data analysis and optimization, and a MapReduce-based algorithm for distributedly and efficiently solving a large-scale version of the problem. We implement the algorithm in the Python programming language and conducted experiments on a Hadoop environment. We study the running time and scalability of the implemented algorithm using small-world random networks and image data for segmentation. We test small-world networks with vertex size ranging from 1000 to 1,000,000; and image grid network with vertex size up to 17000 on single-node and multiple-node Hadoop clusters. We discuss our experience with the possibility and the limitation of the tested MapReduce-based distributed algorithm.

목차

1. 서론

2. 맵리듀스 및 최대흐름 문제의 소개

3. 최대흐름 문제의 맵리듀스 해법

4. 실험

5. 결론

References

키워드

빅 데이터 맵리듀스 네트워크 데이터 분석 최대흐름 문제 Big data Mapreduce Network data analysis Maximum-flow