您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (07): 66-70.doi: 10.6040/j.issn.1671-9352.0.2014.461

• 论文 • 上一篇    下一篇

基于哈希表的MapReduce算法优化

李瑞霞, 刘仁金, 周先存   

  1. 皖西学院信息工程学院, 安徽 六安 237012
  • 收稿日期:2014-10-20 出版日期:2015-07-20 发布日期:2015-07-31
  • 作者简介:李瑞霞(1978-),女,讲师,研究方向为智能数据挖掘及应用.E-mail:lrx0219@wxc.edu.cn
  • 基金资助:
    国家自然科学基金青年基金资助项目(61303209); 六安市定向委托皖西学院市级研究项目(2013LWA004);安徽省教育厅重点项目(KJ2013A255)

Optimization on MapReduce algorithm based on Hash table

LI Rui-xia, LIU Ren-jin, ZHOU Xian-cun   

  1. School of Information Engineering, West Anhui University, Lu'an 237012, Anhui, China
  • Received:2014-10-20 Online:2015-07-20 Published:2015-07-31

PDF (PC)

794

摘要： 分布式并行计算是提高计算机性能常用的方法,但针对不同需求,并行程序的设计并没有统一的模型与方法,使得并行程序的编写完全依靠开发人员的经验。Google公司提出的分布式并行编程模型MapReduce能够完成特定类型的并行程序的开发与运行。使用哈希表对MapReduce分布式并行编程模型进行优化,减少中间结果中的碎片,并省略Combiner中间函数的调用,减少传输负载,提升运行效率,同时兼顾了Map函数与Reduce函数接口的属性,保持了MapReduce模型的并行性特点。

关键词: 分布式, 哈希表, Hadoop, MapReduce, Map函数, 并行

Abstract: Distributed parallel computing is commonly used to improve computer performance. But according to different demands, there is not a uniform way to design and implement parallel program. Parallel programming depends on the experience of developer. MapReduce, a distributed parallel programming model, put forward by Google, can perform special parallel program development and operation. MapReduce was optimized by using Hash table, which would decrease fragment of Map function, skip other redundancy function such as Combiner function, reduce transmission load and improve computing efficiency. Meanwhile, the attributes of Map function and Reduce function were kept to make MapReduce maintaining parallel.

Key words: distributed, MapReduce, Map function, Hash table, parallel, Hadoop

中图分类号: 

  • TP311
[1] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-113.
[2] YANG H, DASDAN A, HSIAO R L, et al. Map-reduce-merge: simplified relational data processing on large clusters[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2007:1029-1040.
[3] APACHE. Welcome to Apache Hadoop[EB/OL].[2014-09-09]. http://hadoop.apache.org/. 2014
[4] 孙牧. 云端的小飞象——Hadoop[J]. 程序员, 2008(10):100-102. SUN Mu. The flying elephant on cloud—Haoop[J]. Journal of Programmer, 2008(10):100-102.
[5] 李成华, 张新访, 金海, 等. MapReduce: 新型的分布式并行计算编程模型[J]. 计算机工程与科学, 2011, 33(3):129-135. LI Chenghua, ZHANG Xinfang, JIN Hai, et al. MapReduce: a new distributed parallel computing programming model[J]. Journal of Computer Engineering and Science, 2011, 33(3):129-135.
[6] 李建江, 崔健, 王聃, 等. MapReduce并行编程模型研究综述[J]. 电子学报, 2011, 39(11):2635-2642. LI Jianjiang, CUI Jian, WANG Dan, et al. Review of MapReduce parallel computing programming model[J]. Chinese Journal of Electronics, 2011, 39(11):2635-2642.
[7] LEISERSON C E, RIVEST R L, STEIN C. Introduction to algorithms[M]. The MIT Press, 2001.
[8] 陈全,邓倩妮.云计算及其关键技术[J].计算机应用,2009,29(9):2562-2567. CHEN Quan, DENG Qianni.Cloud computing and its key techniques[J]. Journal of Computer Applications, 2009, 29(9):2562-2567.
[9] 陆秋,程小辉. 基于MapReduce 的决策树算法并行化[J].计算机应用, 2012, 32(9):2463-2465. LU Qiu, CHENG Xiaohui. Parallelization of decision tree algorithm based on MapReduce[J].Journal of Computer Applications, 2012, 32(9):2463-2465.
[10] 谢桂兰, 罗省贤. 基于 Hadoop MapReduce 模型的应用研究[J]. 微型机与应用, 2010, 25(3):4-7. XIE Guilan, LUO Shengxian. Based on Hadoop MapReduce model apply and research[J]. Journal of Microcomputer and Applications, 2010, 25(3):4-7.
[11] 张雪萍,龚康莉,赵广才. 基于MapReduce的K-Medoids 并行算法[J]. 计算机应用, 2013, 33(4):1023-1025. ZHANG Xueping, GONG Kangli, ZHAO Guangcai. Parallel K-Medoids algorithm based on MapReduce[J].Journal of Computer Applications, 2013, 33(4):1023-1025.
[12] 郭进伟,皮建勇. 基于MapReduce的SON算法实现[J]. 计算机应用,2014, 34(S1):100-102. GUO Jinwei, PI Jianyong. Realization SON algorithm based on MapReduce[J]. Journal of Computer Applications, 2014, 34(S1):100-102.
[13] BONDHUGULA U.Automatic distributed-memory parallelization and code generation using the polyhedral framework, IISc-CSA-TR-2011-3[R].Bangalore: Indian Institute of Science, 2011.
[1] 宋省身,杨岳湘,江宇. 基于单指令级并行的快速求交算法[J]. 山东大学学报（理学版）, 2018, 53(3): 54-62.
[2] 柳欣,徐秋亮,张波. 满足可控关联性的合作群签名方案[J]. 山东大学学报（理学版）, 2016, 51(9): 18-35.
[3] 及歆荣,侯翠琴,侯义斌,赵斌. 基于筛选机制的L1核学习机分布式训练方法[J]. 山东大学学报（理学版）, 2016, 51(9): 137-144.
[4] 卢琦蓓1,2,郭飞鹏3. 基于改进型FP-Tree的分布式关联分类算法[J]. 山东大学学报（理学版）, 2014, 49(1): 71-75.
[5] 郭晓东1,杜鹏1,张雪芬2. 一种WSN中能量有效的分布式检测和功率分配算法[J]. J4, 2012, 47(9): 60-64.
[6] 王侃1,吴磊2,3,郝蓉4. 一个弹性分布式数据安全方案[J]. J4, 2011, 46(9): 39-42.
[7] 陈佩剑1,杨岳湘2,唐川2. 基于信任度量机制的分布式入侵检测系统[J]. J4, 2011, 46(9): 77-80.
[8] 曾剑平,吴承荣,龚凌晖. 面向分布式搜索引擎的索引库动态维护算法[J]. J4, 2011, 46(5): 24-27.
[9] 李宛珊,王文洽*. 二维热传导方程的有限差分区域分解算法[J]. J4, 2011, 46(12): 1-5.
[10] 左进明1,张耀明1,张天德2,李娜2. KuramotoSivashinsky方程的交替分组方法[J]. J4, 2011, 46(12): 29-32.
[11] 付吉美1,左进明2*,张天德1. 五阶色散方程的交替分组方法[J]. J4, 2010, 45(6): 46-49.
[12] 左进明1,张天德2. 五阶色散KdV方程的交替分段显-隐差分格式[J]. J4, 2010, 45(10): 116-121.
[13] 左进明. 五阶色散方程的一类交替分组方法[J]. J4, 2009, 44(4): 79-83 .
[14] 孙凯，王文洽. 抛物型方程的一种高阶并行差分格式[J]. J4, 2009, 44(2): 39-44.
[15] 许秋燕 . 解二维扩散方程的一类有限差分并行算法[J]. J4, 2008, 43(8): 1-05 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发