[논문]빅 데이터 분석을 위한 맵리듀스 알고리즘의 최근 연구 동향

심규석; 김영훈; 이정훈; 김진현; 박윤재

[국내논문] 빅 데이터 분석을 위한 맵리듀스 알고리즘의 최근 연구 동향 원문보기

정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers, v.32 no.1, 2014년, pp.27 - 32

심규석 (서울대학교) , 김영훈 (서울대학교) , 이정훈 (서울대학교) , 김진현 (서울대학교) , 박윤재 (서울대학교)

초록이 없습니다.

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

2이2년 3월 29일 발표 했다. 그 내용의 핵심은 2억불 규모의 연구비를 투입해 다양한 분야에서 축적되고 있는 방대하고 복잡한 데이터로부터 지식과 통찰을 추론해 낼 수 있는 기술을 개발하겠다는 것이다. 이사업에는 미국의 주요 6개 연방 정부 기관이 참여하고 있으며 이 기관들은 다양한 분야의 방대한 디지털데이터를 효율적으로 조직화하고 접근할 수 있도록해주는 기술의 개발과 이 데이터로부터 정보를 추출하는 분석 기술 개발을 위한 연구 과제들을 범정부 차원의 협업을 통해 지원하고 있다.
그래서 빅 데이터 분석 소프트웨어를 쉽게 개발할 수 있는 프로그래밍 모델인 맵리듀스 프레임워크가최근에 관심을 받기 시작했다. 맵리듀스 프레임워크는저렴한 컴퓨터를 수백 수천 대를 연결해서 만든 클러스터에서 병렬 분산 프로그램을 개발할 수 있는 방법론을 제시한다. 구글(Goo이e)의 맵리듀스 또는 오픈 소스 진영에서 만든 하둡(Hadoop)은 그러한 병렬 분산프로그램을 개발하기 위한 맵리듀스 프레임워크를 제공하는 효율적인 툴이다.
여러 응용 분야에서 사용되는 기존에유용하게 사용했던 수많은 순차적 알고리즘들이 빅 데이터도 처리할 수 있기 위해서 맵리듀스 프레임워크를이용한 소프트웨어로 바뀌게 될 것이다. 그렇기 때문에 여기에서는 다양한 분야에서 빅 데이터 분석을 위한 맵리듀스 알고리즘에 대한 최신 연구 동향에 대해서 소개한다.

제안 방법

터 분할 처리에 대한 연구를 수행하였다. 두 테이블의모든 레코드의 쌍을 2차원 배열로 표시하고 여기서 조인 질의의 결과로 나타날 인접한 부분들을 묶어서 몇개의 영역으로 나눈 뒤 이 영역들을 하나의 리듀스 함수에서 처리하는 방법을 제안하였다.
터 분할 처리에 대한 연구를 수행하였다. 두 테이블의모든 레코드의 쌍을 2차원 배열로 표시하고 여기서 조인 질의의 결과로 나타날 인접한 부분들을 묶어서 몇개의 영역으로 나눈 뒤 이 영역들을 하나의 리듀스 함수에서 처리하는 방법을 제안하였다. N-way 조인 알고리즘의 수행에 대한 병렬 알고리즘은 [28-3이에서 연구되었다.
[3기에서는 L2 norm에 대한 웨이블릿 계수를 top-K 알고리즘을 이용하여 정확하게 계산하는 방법을 제안했고 이 때의 많은 데이터 통신량(communication cost)을 줄이기 위해 웨이블릿 계수의 불편 추정량(unbiased estimator)을통한 샘플링 방식을 제안하였다.

참고문헌 (38)

J. B. MacQueen. Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, pp.281-297. 1967.
Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, Prabhakar Raghavan. Automatic subspace clustering of high dimensional data for data mining applications. ln SIGMOD, 1998.
Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, 1996.
Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jorg Sander. OPTICS: Ordering Points To Identify the Clustering Structure. In STGMOD, 1999.
장지훈, 박형민, 심규석, 맵리듀스 프레임웍을 이용한 서브스페이스클러스터링의 구현, 한국정보과학회학술발표눈문집, 제35권, 제2호, pp.98-103, 2008.
Yaobin He, Haoyu Tan, Wuman Luo, Huajian Mao, Di Ma, Shengzhong Feng, Jianpillg Fan. MR-dbscan: An efficient parallel density-based clustering algorithm using MapReduce. In ICPADS, 2011.
Younghoon Kim, Kyuseok Shim, Min-Soeng Kim, June Sup Lee, DBCURE-MR: An efficient density based clustering algorithm for large data using MapReduce, To appear to Information Systems.
Tianyang Sun, Chengchun Shu, Feng Li, Haiyan Yu, Lili Ma, Yitong Fang. An efficient hierarchical clustering method for large datasets with Map-Reduce. In PDCAT,2009.
Meghana Deodhar, Joydeep Ghosh. A framework for simultaneous co-clustering and learning from complex data. In KDD, 2007.
Meghana Deodhar, Clinton Jones, and Joydeep Ghosh. Parallel Simultaneous Co-clustering and Learning with Map-Reduce. In IEEE International Conference on Granular Computing, 2010.
Jiawei Han, Jian Pei, and Yiwen Yin. Mining frequent patterns without candidate generation. In SlGMOD, 2000.
Jiawei Han, Jian Pei, Yiwen Yin. Mining frequent patterns without candidate generation. In SIGMOD, 2000.
Biswanath Panda, Joshua. S. Herbach, Sugato Basu, and Roberto J. Bayardo. PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce. In VLDB, 2012.
김영훈, 심규석,맵리듀스를 이용한 아다부스트 알고리즘,Telecommunication Reviews(SK Telecom), " 제21권, 제3호, 2011
Chao Liu, Hung-Chih Yang, Jinliang Fan, Li-Wei He, and Yi-Min Wang. Distributed nonnegative matrix factorization for web-scale dyadic data analysis on mapreduce. In WWW, 2010.
U Kang, Brendan Meeder, and Christos Faloutsos. Spectral analysis for billion-scale graphs: Discoveries and implementation. In PAKDD, 2011.
U Kang, Charalampos E. Tsourakakis, and Christos Faloutsos. PEGASUS: Mining Peta-scale Graphs. Knowledge and Infonnation Systems, Vol. 27, No.2, pp. 303-325,2011.

상세보기
Siddharth Suri, and Sergei Vassilvitskii. Counting triangles and the curse of the last reducer. In WWW, 2011.
Ha-Myung Park, and Chin-Wan Chung. An efficient MapReduce algorithm for counting triangles in a very large graph. In ClKM, 2013.
정우환, 김영훈, 심규석, 그래프의 삼각형 개수 계산을 위한 맵리듀스 알고리즘, 한국정보과학회 학술발표논문집, 제39권, 제2호, pp.16-18, 2012.
James W. Demmel. Applied numerical linear algebra, SIAM, 1997.
Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Google news personalization: scalable online collaborative filtering. In WWW, 2007.
Younghoon Kim, and Kyuseok Shim. TWITOBI: A Recommendation System for Twitter Using Probabilistic Modeling. In ICDM, 2011.
Yi Wang, Hongjie Bai, Matt Stanton, Wen-Yen Chen, and Edward Y. Chang. PLDA: Parallel latent dirichlet allocation for large-scale applications. In AAlM, 2009.
Ke Zhai, Jordan Boyd-Graber, Nima Asadi, and Mohamad Alkhouja. Mr. LDA: A flexible large scale topic modeling package using variational inference in MapReduce. In WWW, 2012.
Huanhuan Cao, Daxin Jiang, Jian Pei, Enhong Chen, and Hang Li . Towards Context-Aware Search by Learning A Very Large Variable Length Hidden Markov Model from Search Logs. In WWW, 2009.
Alper Okcan, Mirek Riedewald. Processing theta-joins using MapReduce. In SIGMOD, 2011.
Foto N. Atrati, Jeffrey D. Ullman. Optimizing joins in a Map-Reduce environment. In VLDB, 2009.
Xiaofei Zhang, Lei Chen, Min Wang. Efficient Multiway Theta-loin Processing Using MapReduce. In VLDB, 2012.
Sai Wu, Feng Li, Sharad Mehrotra, Beng Chin Ooi. Query optimization for massively parallel data processing. In SOCC, 2011.
Rares Vernica, Michael J. Carey, Chen Li. Efficient parallel set-similarity joins using MapReduce. In SIGMOD, 2010.
Ahmed Metwally, Christos Faloutsos. V-SMART-Join: A scalable MapReduce framework for all-pair similarity joins of multisets and vectors. In VLDB, 2012.
Younghoon Kim, Kyuseok Shim. Parallel top-k similarity join algorithms using MapReduce. In ICDE, 2012.
Ranieri Baraglia. Gianmarco De Francisci Morales, Claudio Lucchese. Document similarity self-join with MapReduce. In ICDM, 2010.
Tamer Elsayed, Jimmy J. Lin, Douglas W. Oard. Pairwise document similarity in large collections with MapReduce. In HLT, 2008.
Yoonjae Park, Jun-Ki Min, and Kyuseok Shim. Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce. Proceedings of the VLDB Endowment, Vol. 6, No. 14, 2013.
Jeffrey Jestes, Ke Yi, and Feifei Li. Building Wavelet Histograms on Large Data in MapReduce. Proceedings of the VLDB Endowment, Vol. 5, No.2, pp.109-1 02, 2011.
Yufei Tao, Wenqing Lin and Xiaokui Xiao. Minimal MapReduce algorithms. In SIGMOD, 2013.

저자의 다른 논문 :

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증