맵리듀스를 활용한 새로운 분산 병렬 비트큐브 알고리즘
A Novel Distributed Parallel BitCube Algorithm via MapReduce FrameWork
- 발행기관 서강대학교 정보통신대학원
- 지도교수 장형수
- 발행년도 2012
- 학위수여년월 2012. 8
- 학위명 석사
- 학과 및 전공 정보통신대학원 정보처리
- 실제URI http://www.dcollection.net/handler/sogang/000000047800
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록/요약
대용량 데이터 분석시 많은 집계 연산을 수행하는데, 데이터 양이 커짐에 따라 처리시간의 증가와 메모리 공간의 제약을 받게 된다. 이와 같은 대용량 데이터 분석을 위해 데이터 큐브를 활용하는데, 대표적인 데이터큐브 알고리즘으로 Multi-Way array aggregation, BUC, Star-cubing 알고리즘을 들 수 있다. Multi-Way array aggregation 나 BUC 알고리즘은 배열을 이용한 데이터 큐브 생성 기법으로 데이터 큐브 생성 시 막대한 메모리 사용이 발생한다. 또한 Star-cubing 알고리즘은 데이터 큐브 생성을 위해 모든 큐보이드를 트리로 구축해야 하고, 집계연산을 위해서는 모든 트리를 검색해야 하는 연산비용이 증가한다. 본 논문에서는 이러한 문제점들을 해결하기 위해 네트워크로 연결된 여러 컴퓨터를 이용해 대용량의 문제를 분산하여 처리하는 맵리듀스(MapReduce) 프레임워크를 활용한 비트큐브(BitCube) 알고리즘을 제안한다. 맵리듀스 프레임워크를 기반으로 한 병렬/분산 컴퓨팅 환경에서 비트맵 구조의 역색인(Inverted index) 를 활용하여 입력 데이터의 위치를 저장하고, 비트맵 정보들 간의 AND 비트연산을 통해 큐보이드를 생성한다. 본 논문은 데이터 처리 방식에 따라 비트큐브-MR, 비트큐브-MCR, 비트큐브-M 3가지 알고리즘을 설계하였다. 비트큐브-MR 알고리즘은 맵 함수에서 읽어 들인 데이터를 리듀스 함수로 전달하고, 집계연산을 수행한 후 최종 결과값을 방출한다. 이 과정을 대용량 데이터에 대한 집계연산을 다수의 프로세서에 의해 분산 병렬 처리함으로써 성능 향상을 얻을 수 있다. 다만, 비트큐브-MR 알고리즘은 맵 함수에서 방출되는 과도한 데이터로 인한 네트워크 부하가 발생하는 단점이 있다. 비트큐브-MCR 알고리즘은 네트워크 부하 문제를 해결하기 위해 방안으로 맵 함수에서 방출되는 데이터를 같은 키에 의한 사전 집계를 하고, 조건을 만족하는 데이터만을 방출하는 필터링 기법을 설계하였다. 이를 통해 리듀스 함수로 전달되는 데이터를 최소화하여 네트워크 부하 문제를 개선하였다. 마지막으로, 비트큐브-M 알고리즘은 밸류 파티셔닝(Value Partitioning) 기법과 로컬 어그리게이션(Local Aggregation) 기법을 디자인하였다. 밸류 파티셔닝이란 대량 데이터를 분할하여 각 프로세서로 분산하여 저장하는 전처리 기법이다. 로컬 어그리게이션은 맵 함수에서 리듀스 함수로 데이터를 전달하는 과정을 없애고, 맴 함수에 의해 집계연산을 직접 처리하는 기법이다. 이를 통해 네트워크 부하 문제를 해결하였고, 대용량 데이터의 집계연산에 대한 효율적인 분산 병렬처리를 함으로써 뛰어난 성능 향상을 얻을 수 있었다.
more초록/요약
When analyzing large amounts of data with many aggregations, growing amount of data causes various problems such as an increase in processing time and memory limitation. Data cubes are structures used for large amounts of data analysis. Multi-way Array aggregation, Bottom-Up Computation (BUC) and Star-Cubing are typical data cube algorithms. Multi-Way array aggregation and BUC which are using an array in creating a data cube generates a huge memory usage. While Star-cubing algorithm generates all cuboids into tree for the data cube, and searches all the tree for aggregation which increases the cost of operation. In this paper, distributed parallel BitCube algorithm is proposed to solve the problems by using MapReduce framework consisting of multiple networked computers to handle large data problems. Based on MapReduce framework for parallel/distributed computing environment, BitCube Algorithm uses a bitmap structure in the inverted index to store the location of the input data and generates cuboids from AND bit operations between the bitmaps. This study designed three different algorithms, BitCube-MR, BitCube-MCR and BitCube-M. BitCube-MR reads data from map function and passes it to reduce function to aggregate and emits the final results. During this process, performance improvement can be obtained by a distributed parallel processing on a large number of processors. However, BitCube-MR has the disadvantage which causes excessive network load due to too many data from map function. BitCube-MCR algorithm is designed from filtering techniques to solve the network load problem in ways that collects data with the same keys from map function and emits only the data satisfying the certain condition. Finally, BitCube-M algorithm is designed from Value Partitioning and Local Aggregation techniques. Value Partitioning is a technique which splits large amount of data and store them into each processors on distributed environment. Local aggregation eliminates data passing to reduce function and handles aggregate operation directly in map function. By this process, the network load can be solved and performance improvement could be obtained by efficient distributed parallel processing for large amount of data aggregation.
more