맵리듀스를 사용한 데이터 큐브의 효율적인 계산 기법
Efficient Computation of Data Cubes Using MapReduce
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
맵리듀스(MapReduce)는 대용량 데이터를 다수의 컴퓨터로 병렬 처리하는 데 사용되는 프로그래밍 모델이다. 데이터 큐브(Data Cube)는대용량 데이터 분석에 널리 사용되는 연산자로서, 주어진 차원 애트리뷰트들의 모든 가능한 조합에 대한 group-by들을 계산한다. 차원 애트리뷰트의 개수가 n일 때, 데이터 큐브는 총 2n개의 group-by를 계산한다. 본 논문은 맵리듀스를 사용하여 데이터 큐브를 효율적으로 계산하는 방법을 제안한다. 제안 방법은 2n개의 group-by를 n C⌈n/2⌉개의 그룹으로 분할하고, 이 그룹들을 ⌈n/2⌉개의 맵리듀스 잡(job)을 통해 단계적으로 계산한다. 제안 방법은 기존 방법에 비해 맵퍼(mapper)가 생성하는 중간결과의 크기를 크게 줄임으로써 중간결과의 전송 및정렬에 드는 비용을 크게 줄인다. 그에 따라 데이터 큐브를 계산하는 총 수행시간이 크게 감소된다. 실험을 통해 제안 방법이 기존 방법에비해 더 빠르게 데이터 큐브를 계산함을 보인다.
Abstract
MapReduce is a programing model used for parallelly processing a large amount of data. To analyze a large amount data, the datacube is widely used, which is an operator that computes group-bys for all possible combinations of given dimension attributes. Whenthe number of dimension attributes is n, the data cube computes 2n group-bys. In this paper, we propose an efficient method forcomputing data cubes using MapReduce. The proposed method partitions 2n group-bys into n C⌈n/2⌉ batches, and computes thosebatches in stages using ⎡n/2⌉ MapReduce jobs. Compared to the existing methods, the proposed method significantly reduces theamount of intermediate data generated by mappers, so that the cost of sorting and transferring those intermediate data is reducedsignificantly. Consequently, the total processing time for computing a data cube is reduced. Through experiments, we show theefficiency of the proposed method over the existing methods.
참고문헌 (15)
- Mark Beyer, "Gartner Says Solving ‘Big Data’ Challenge Involves More Than Just Managing Volumes of Data", Gartner, ~ (2011)
- Jeffrey Dean, "MapReduce: simplified data processing on large clusters", In Proceedings of OSDI ’04, pp.137~150 (2004)
- J. Gray, "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals", In Proceedings of the ICDE Conference, pp.152~159 (1996)
- Arnab Nandi, "Data Cube Materialization and Mining over MapReduce", IEEE Transactions on Knowledge and Data Engineering, 24(10), pp.1747~1759 (2012)
- Zhengkui Wang, "Scalable Data Cube Analysis over Big Data", CoRR, abs, 2013
- Wang, Yuxiang, "A mapreducemerge-based data cube construction metho", In Proceedings of IEEE International Conference on Grid and Cooperative Computing(GCC), pp.1~6 (2010)
- Sergey, Kuznecov, "Applying map-reduce paradigm for parallel closed cube computation", In Proceedings of IEEE International Conference on Advances in Databases, Knowledge, and Data Applications, pp.62~67 (2009)
- You, Jinguo, "A parallel algorithm for closed cube computation", In Proceedings of IEEE, 2008, 95~99
- Venky Harinarayan, "Implementing Data Cubes Efficiently", In Proceedings of ACM SIGMOD, pp.205~216 (1996)
- Kevin Beyer, "Bottom-Up Computation of Sparse and Iceberg Cube", In Proceedings of ACM SIGMOD, pp.359~370 (1999)
- Guoping Wang, "Multi-Query Optimization in MapReduce Framework", PVLDB, 7(3), pp.145~156 (2013)
- Lakshmanan, Laks VS, "Quotient cube: How to summarize the semantics of a data cube", In Proceedings of the 28th international conference on Very Large Data Bases, pp.778~789 (2002)
- Wang, Wei, "Condensed cube: An effective approach to reducing data cube size", In Proceedings of IEEE International Conference on Data Engineering, pp.155~165 (2002)