맵리듀스 환경에서 웨이블릿 시놉시스 생성 알고리즘 (A Wavelet Synopsis Generation Algorithm in the MapReduce Framework)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 39권 / 6호 / 346 ~ 353페이지
· 저자명 : 김철연

초록

웨이블릿은 데이터베이스 시스템의 질의최적화, 개략 질의처리와 멀티미디어 데이터에 대한 특징 추출 등에 사용되어 온 대표적인 정보 개략화 알고리즘으로 원본 데이터의 정보 손실을 최소화하는 최적의 시놉시스를 생성하는 알고리즘이다. 맵리듀스는 분산처리를 위한 플랫폼으로 구글의 데이터 처리를 위한 플랫폼으로 사용되어 최근 다양한 분야에서 각광을 받고 있다. 맵리듀스 플랫폼은 분산 파일시스템에 저장되어 있는 데이터들을 맵과 리듀스의 2단계 분산 프로세스로 데이터를 처리하는 구조를 가지고 있으며, 다양한 기존의 알고리즘들이 이러한 맵리듀스 플랫폼 상에서 실행될 수 있도록 재구성되고 있다. 이에 본 논문에서는 분산된 맵리듀스 환경에서의 웨이블릿 시놉시스 생성 알고리즘을 제안한다. 제안하는 알고리즘은 한번의 맵리듀스 절차를 통해 웨이블릿 시놉시스를 분산 환경에서 계산할 수 있으며, 분산환경의 네트워크상의 데이터 교환을 최소화하여 선형의 시간복잡도 내에서 최적의 웨이블릿 시놉시스를 계산한다.

영어초록

The Wavelet synopsis is a representative dimensionality reduction method and has been popularly used in query optimization, approximate query answering, feature selection from multimedia data, etc. The MapReduce is a distributed platform which is well known as Google’s data processing platform. A MapReduce phase consists of consecutive map and reduce steps, and many traditional algorithms are being converted to be executable in the MapReduce platform. In this paper we propose a new algorithm to generate wavelet synopses in the distributed MapReduce framework. In the proposed algorithm, the optimal wavelet synopsis can be generated by a single MapReduce phase, and, by minimizing the amount of data communicated through the network of the distributed MapReduce platform, all computations are processed within a linear time complexity.

참고자료

· 없음