맵리듀스를 이용한 데이터 큐브의 상향식 계산을 위한 반복적 알고리즘
An Iterative Algorithm for the Bottom Up Computation of the Data Cube using MapReduce
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
최근 데이터의 폭발적인 증가로 인해 대규모 데이터의 분석에 대한 요구를 충족할 수 있는 방법들이 계속 연구되고 있다. 본 논문에서는 맵리듀스를 이용한 분산 병렬 처리를 통해 대규모 데이터 큐브의 효율적인 계산이 가능한 MRIterativeBUC 알고리즘을 제안하였다. MRIterativeBUC 알고리즘은 기존의 BUC 알고리즘을 맵리듀스의 반복적 단계에 따른 효율적인 동작이 가능하도록 개발되었고, 기존의 대규모 데이터 큐브 계산에 따른 문제인 데이터 크기와 저장 및 처리 능력의 한계를 해결하였다. 또한, 분석자의 관심 부분에 대해서만 계산하는 빙산 큐브 개념의 도입과 파티셔닝, 정렬과 같은 큐브 계산을 분산 병렬 처리하는 방법 등의 장점들을 통해 데이터 방출량을 줄여서 네트워크 부하를 줄이고, 각 노드의 처리량을 줄이며, 궁극적으로 전체 큐브 계산 비용을 줄일 수 있다. 본 연구결과는 맵리듀스를 이용한 데이터 큐브 계산에 대해서 상향식 처리와 반복적 알고리즘을 통해 다양한 확장이 가능하며, 여러 응용 분야에서 활용이 가능할 것으로 예상된다.
Abstract
Due to the recent data explosion, methods which can meet the requirement of large data analysis has been studying. This paper proposes MRIterativeBUC algorithm which enables efficient computation of large data cube by distributed parallel processing with MapReduce framework. MRIterativeBUC algorithm is developed for efficient iterative operation of the BUC method with MapReduce, and overcomes the limitations about the storage size and processing ability caused by large data cube computation. It employs the idea from the iceberg cube which computes only the interesting aspect of analysts and the distributed parallel process of cube computation by partitioning and sorting. Thus, it reduces data emission so that it can reduce network overload,processing amount on each node, and eventually the cube computation cost. The bottom-up cube computation and iterative algorithm using MapReduce, proposed in this paper, can be expanded in various way, and will make full use of many applications.
참고문헌 (25)
- Gray, J., "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals", In Proc. Conf. on Data Engineering, pp.152~199 (1996)
- Harinarayan, V., "Implementing Data Cubes Efficiently", In Proc.Int'l Conf. on Management of Data, ACM SIGMOD, pp.205~216 (1996)
- Agarwal, S., "On the Computation of Multidimensional Aggregates", In Proc. the 22nd Int'l Conf. on Very Large Data Bases, pp.506~521 (1996)
- Ross, K. A., "Fast Computation of Sparse Datacubes", In Proc. the 23rd Int'l Conf. on Very Large Data Bases, pp.116~125 (1997)
- Li, X., "High-dimensional OLAP: A Minimal Cubing Approach", In Proc. the 30th Int'l Conf. on Very Large Data Bases, pp.528~539 (2004)
- Beyer, K., "Bottom-Up Computation of Sparse and Iceberg Cubes", In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, pp.359~370 (1999)
- Han, J., "Efficient Computation of Iceberg Cubes with Complex Measures", In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, pp.1~12 (2001)
- Shao, Z., "MM-Cubing: Computing Iceberg Cubes by Factorizing the Lattice Space", In Proc. 16th Int'l Conf. of Scientfic and Statistical Database Management, pp.213~ (2004)
- Xin, D., "Star-cubing: Computing Iceberg Cubes by Top-down and Bottomup Integration", In Proc. 29th Int'l Conf. of Very Large Data Bases, pp.476~487 (2003)
- Dean, J., "MapReduce : Simplified Data Processing on Large Clusters", Communication of the ACM, 51(1), pp.107~113 (2008)
- Ying, C., "Parallel ROLAP Data Cube Construction on Shared-Nothing Multiprocessors", Distributed and ParallelDatabases, 15(3), pp.219~236 (2004)
- Frank, D., "The cgm- CUBE Project: Optimizing Parallel Data Cube Generation for ROLAP", Distributed and Parallel Databases, 19(1), pp.29~62 (2006)
- Chen, Y., "PnP : Parallel And External Memory Iceberg Cube Computation", Distributed and Parallel Databases, 23(2) (2008)
- T. Ng, R., "Iceberg-cube computation with PC clusters", In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, pp.25~36 (2001)
- Agrawal, R., "Mining Association Rules between Sets of Items in Large Databases", In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, pp.207~216 (1993)
- Jinguo, Y., "A Parallel Algorithm for Closed Cube Computation", In Proc. 7th Int'l Conf. on Computer and Information Science, pp.95~99 (2008)
- Yuxiang, W., "A Map-ReduceMerge-based Data Cube Construction Method", In Proc. 9th Int'l Conf. on Grid and Cooperative Computing, pp.1~6 (2010)
- Suan, L., "Distributed Parallel Top-Down Computation of Data Cube using MapReudce", In Proc. 3rd Int'l Conf. on Emerging Databases, pp.303~306 (2011)
- Arnab, N., "Distrubuted Cube Materialization on Holistic Measures", In Proc. 27th Int'l Conf. on Data Engineering, pp.183~194 (2011)
- Ghemawat, S., "The Google File System", In Proc. 19th on Operating Systems Principles, pp.29~43 (2003)
- "Hadoop"[URL]
- "HDFS"[URL]
- 김현수, "온톨로지와 시각화가 적용된 기술참조모델(TRM)의 활용방안에 관한 연구", 정보기술아키텍처 연구, 8(4), pp.347~360 (2011), 한국ITA학회
- 이우기, "Mobile Web Navigation in Digital Ecosystems Using Rooted Directed Trees", IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS, 58(6), pp.2154~2162, IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
- 이우기, "웹 아키텍처에 대한 그래프 기반 평가방법", 정보기술아키텍처 연구, 4(1), pp.61~69 (2007), 한국ITA학회