이학석사학위논문  맵리듀스 프레임워크를 이용한   빙산 큐브의 상향식 계산  이 수 안  강원대학교대학원  컴퓨터과학과  2010년 2월  김진호 교 수 지 도  이학석사학위논문  맵리듀스 프레임워크를 이용한   빙산 큐브의 상향식 계산  bottom up computation of iceberg cube   using mapreduce framework  강원대학교대학원  컴퓨터과학과  이 수 안  이수안의 석사학위논문을   합격으로 판정함  2009년 12월  심사위원장 인  위 원 인  위 원 인  맵리듀스 프레임워크를 이용한   빙산 큐브의 상향식 계산  이 수 안  강원대학교대학원 컴퓨터과학과  

최근 정보 기술과 웹의 발전으로 인해, 많은 응용에서 대용량 데이터의 저장 및 분석이 요구되고 있다. 대용량 데이터의 효율적 분석을 위해 데이터 큐브가 연구되었으며, 데이터 큐브 계산의 고비용 문제점을 해결하기 위하여, 큐브의 일부 영역만을 계산하는 빙산 큐브가 등장하였다

빙산 큐브는 저장 공간의 감소, 집중적인 분석 등의 장점이 있으나, 여전히 많은 계산과 저장 공간을 필요로 하는 단점이 있다. 본 논문에서는 이러한 문제점을 해결하는 실용적인 방법으로 맵리듀스(mapreduce) 프레임워크를 사용한 분산 병렬 빙산 큐브 계산을 제안한다

맵리듀스 프레임워크는 네트워크로 연결된 여러 컴퓨터의 처리 능력을 이용하여 대용량 문제를 분산하여 처리하는 분산 병렬 컴퓨팅 기술이다. 본 논문에서는 맵리듀스 프레임워크를 사용한 빙산 큐브 계산 알고리즘으로서, mr-naive와 mr-buc를 제안한다

mr-naive는 빙산 큐브의 임계치(min sup)를 맵리듀스 프레임워크의 후반부에 적용한 알고리즘으로, 그 동작 절차는 다음과 같다. 먼저, 전체 큐보이드를 맵리듀스의 맵(map) 함수를 사용하여 여러 컴퓨터에 분산한다

그런 다음, 각 컴퓨터는 해당 큐보이드를 계산하고, 그 결과를 리듀스(reduce) 함수를 사용하여 수집한 후 집계한다. 집계 결과가 임계치 이상인 경우에 한해 최종 결과로서 반환한다

다음으로, mr-buc는 임계치를 맵리듀스 프레임워크의 전반부에 적용한 알고리즘으로, 그 동작 절차는 다음과 같다. 먼저, 데이터들에 대한 파티셔닝과 전지를 통해 임계치를 만족하는 데이터만을 맵 함수를 통해 컴퓨터들에 분산한다

그런 다음, 각 컴퓨터는 해당 데이터에 대한 집계를 수행하고, 그 결과를 취합하여 최종 결과로 반환한다. 실험 결과, 제안한 mr-naive와 mr-buc는 프로세서가 증가함에 따라 계산 성능이 증가하였으며, 대부분의 경우에 있어서 기존 알고리즘에 비해 우수한 성능을 나타내었다

특히, 차원이 낮은 경우에는 mr-naive가, 차원이 높은 경우에는 mr-buc가 가장 좋은 성능을 나타내었다. 이는 맵 함수를 전반부에 수행하느냐, 후반부에 수행하느냐의 차이에 따른 것으로, 사용자는 주어진 데이터 특성에 따라 mr-naive 혹은 mr-buc를 선택하여 빙산 큐브 계산의 성능을 극대화할 수 있다

본 연구는 맵리듀스 프레임워크를 이용한 빙산 큐브 계산의 첫 번째 시도로서, 맵리듀스 프레임워크를 통해 빙산 큐브 계산이 효율적으로 분산 병렬 처리됨을 확인하였다.
목 차
1.
서 론   1  
2.
관련 연구   5  
2.1 데이터 큐브와 빙산 큐브
5  
2.2 빙산 큐브 계산 알고리즘
8  
2.2.1 하향식 빙산 큐브 계산
8     (이하 생략)