대용량 데이터를 위한 맵리듀스 프레임워크 기반의 효율적인 요약정보 생성 기법 (An Efficient Synopsis Construction Algorithm based on MapReduce Frameworks for Big Data)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 31권 / 2호 / 70 ~ 83페이지
· 저자명 : 김홍연, 이석주, 강성민, 민준기

초록

디지털 데이터의 양이 기하급수적으로 증가함에 따라 데이터를 효과적으로 분석하기 위한 데이터의 요약정보가 점차 중요해지고 있다. 본 논문에서는 맵리듀스 프레임워크를 이용하여 대용량 데이터에 대한 q-digest를 생성하는 eqMR과 nqMR을 제안한다. q-digest는 데이터 값들의 빈도수들을 표현하는 요약정보로 데이터에 대한 분위값을 계산하는데 효과적이다. 그러나 기존 q-digest 생성 기법은 단일기기를 기반으로 하여서 빅 데이터에는 적합하지 않다. 이러한 문제를 해결하기 위해, eqMR 기법은지역 q-digest들을 복수 개의 기기를 이용하여 병렬로 생성하고 이들을 병합하여 전역 q-digest를 생성한다. 추가적으로 nqMR 기법은 데이터 집합의 분포를 파악하여 지역 q-digest들의 생성에 따른 기기들의 부하를 줄인다. 실험에서는 다양한 환경에서 성능 평가를 수행하였다.

영어초록

As the size of digital data increases, the synopses of the data become important to analyze the data effectively. In this paper, we propose two algorithms eqMR and nqMR that construct the q-digest over the massive data using MapReduce frameworks. The q-digest representing the frequencies of the data item is an effective synopsis to compute the quantiles. However, since the existing q-digest construction algorithm is based on a single-machine, it is not suitable to the big data. To alleviate this problem, the eqMR algorithm constructs the local q-digests using several machines in parallel and merges the local q-digests to construct the global q-digest. Additionally, the nqMR algorithm reduces the load of the machines depending on the local q-digest construction by identifying the data distribution. In experiments, we evaluated the performance of our algorithms in diverse environments.

참고자료

· 없음