基于MapReduce模型的排序算法优化研究

发布时间：2018-06-18 04:28

  本文选题：MapReduce模型 + 优化算法　； 参考：《计算机科学》2014年12期

【摘要】：MapReduce已经发展成为大数据领域标准的并行计算模型。理想情况下,一个MapReduce系统应该使参与计算的所有节点高度负载均衡,并且最小化空间使用率、CPU和I/O的使用时长以及网络传输开销。传统的算法往往只针对上述指标中的一种进行优化。在保持算法良好并行性基础上,对多个指标同时进行优化,提出了MapReduce优化算法的设计规范。针对数据处理领域最重要的排序算法进行理论分析,给出了多指标约束下的最后算法,并证明了该优化算法满足MapReduce优化算法规范。最后通过实验验证了优化的排序算法的有效性和效率。
[Abstract]:MapReduce has developed into a standard parallel computing model in the big data domain. Ideally, a MapReduce system should have a high load balance for all nodes involved in the calculation, and minimize space usage, CPU and I / O usage times and network transmission overhead. The traditional algorithms are usually optimized for one of the above indexes. On the basis of preserving the good parallelism of the algorithm, several indexes are optimized simultaneously, and the design criterion of MapReduce optimization algorithm is proposed. Based on the theoretical analysis of the most important sorting algorithm in the field of data processing, the final algorithm under multi-index constraints is presented, and it is proved that the optimization algorithm meets the MapReduce optimization criterion. Finally, the effectiveness and efficiency of the optimized sorting algorithm are verified by experiments.
【作者单位】： 北京理工大学软件学院;
【分类号】：TP311.13

【参考文献】

相关期刊论文 前5条

1 程兴国;肖南峰;;粗粒度并行遗传算法的MapReduce并行化实现[J];重庆理工大学学报(自然科学);2013年10期

2 鲁伟明;杜晨阳;魏宝刚;沈春辉;叶振超;;基于MapReduce的分布式近邻传播聚类算法[J];计算机研究与发展;2012年08期

3 亓开元;韩燕波;赵卓峰;房俊;;支持高并发数据流处理的MapReduce中间结果缓存[J];计算机研究与发展;2013年01期

4 和亮;冯登国;王蕊;苏璞睿;应凌云;;基于MapReduce的大规模在线社交网络蠕虫仿真[J];软件学报;2013年07期

5 刘义;景宁;陈荦;熊伟;;MapReduce框架下基于R-树的k-近邻连接算法[J];软件学报;2013年08期

【共引文献】

相关期刊论文 前10条

1 郎波;张博宇;;面向大数据的非结构化数据管理平台关键技术[J];信息技术与标准化;2013年10期

2 邵景峰;崔尊民;王进富;白晓波;;大数据下纺织制造执行系统的构建[J];纺织器材;2013年06期

3 张亚楠;谭跃生;;基于MapReduce的并行遮盖文本聚类算法[J];内蒙古科技大学学报;2013年03期

4 周国亮;朱永利;王桂兰;;CC-MRSJ:Hadoop平台下缓存敏感的星型联接算法[J];电信科学;2013年10期

5 王鹏;黄焱;刘峰;安俊秀;;大数据技术中计算与数据的协作机制[J];成都信息工程学院学报;2014年01期

6 杜政颉;王鹏;黄焱;郎福通;;一种基于Storm编程模型的迭代Topology方案[J];成都信息工程学院学报;2014年01期

7 范飞;黄文明;邓珍荣;;Oozie工作流在Mahout分布式数据挖掘中的应用[J];桂林电子科技大学学报;2014年01期

8 丁玉成;诸葛晴凤;沙行勉;;云计算环境下排序算法的性能分析[J];重庆大学学报;2014年04期

9 乔媛媛;刘芳;凌艳;尹劲松;;云计算环境下MapReduce的资源建模与性能预测[J];北京邮电大学学报;2014年S1期

10 刘琼;赵荣;孙立坚;;Map/Reduce框架下的粗糙集空间数据挖掘改进算法[J];测绘科学;2014年05期

相关会议论文 前5条

1 乔媛媛;刘芳;凌艳;尹劲松;;云计算环境下MapReduce的资源建模与性能预测[A];2013年全国通信软件学术会议论文集[C];2013年

2 Xiaoguang Han;Jigang Sun;Wu Qu;Xuanxia Yao;;Distributed Malware Detection based on Binary File Features in Cloud Computing Environment[A];第26届中国控制与决策会议论文集[C];2014年

3 陈佐旗;余柏蒗;吴健平;;基于GPU通用计算的遥感数据处理——以计算地表太阳辐射值为例[A];第十八届中国环境遥感应用技术论坛论文集[C];2014年

4 白永超;付伟;辛阳;;基于Hadoop和Nutch的分布式搜索引擎研究与仿真[A];第十九届全国青年通信学术年会论文集[C];2014年

5 李超越;徐国胜;;Hadoop公平调度算法的改进[A];第十九届全国青年通信学术年会论文集[C];2014年

相关博士学位论文 前10条

1 李健;云计算环境下最小化运营开销的调度技术研究[D];北京邮电大学;2013年

2 韩晶;大数据服务若干关键技术研究[D];北京邮电大学;2013年

3 程祥;高效可靠的虚拟网络映射技术研究[D];北京邮电大学;2013年

4 李韧;基于Hadoop的大规模语义Web本体数据查询与推理关键技术研究[D];重庆大学;2013年

5 卢风顺;面向CPU/GPU异构体系结构的并行计算关键技术研究[D];国防科学技术大学;2012年

6 孙鹏;动车组维修物联网及其关键技术研究[D];中国铁道科学研究院;2013年

7 肖奎;维基百科大数据的知识挖掘与管理方法研究[D];武汉大学;2013年

8 程兴国;仿生算法的动态反馈机制及其并行化实现方法研究[D];华南理工大学;2013年

9 马冯;数据密集型计算环境下贝叶斯网的学习、推理及应用[D];云南大学;2013年

10 韩海雯;MapReduce计算任务调度的资源配置优化研究[D];华南理工大学;2013年

相关硕士学位论文 前10条

1 黄国臣;护理床动作控制的个性化推荐模式研究[D];广东工业大学;2013年

2 张鑫;动态复杂网络中增量式社团发现方法的研究与实现[D];西安电子科技大学;2013年

3 陈贞;HDFS环境下的访问控制技术研究[D];重庆大学;2013年

4 张丹;HDFS中文件存储优化的相关技术研究[D];南京师范大学;2013年

5 潘吴斌;基于云计算的并行K-means气象数据挖掘研究与应用[D];南京信息工程大学;2013年

6 赵洪昌;云计算下的关联分析和模糊聚类研究[D];南京信息工程大学;2013年

7 汪洋;通信网云计算平台资源调度策略与算法研究[D];南昌大学;2013年

8 吕天然;基于MapReduce的可视化工作流遥感并行处理平台及关键技术研究[D];河南大学;2013年

9 但光祥;云计算环境下混合加密算法研究与实现[D];重庆大学;2013年

10 周涛;基于Hadoop的遥感数字图像处理方法研究[D];东北师范大学;2013年

【二级参考文献】

相关期刊论文 前9条

1 倪巍伟,陆介平,孙志挥;基于向量内积不等式的分布式k均值聚类算法[J];计算机研究与发展;2005年09期

2 罗卫敏;刘井波;刘静;陈晓峰;;XSS蠕虫在社交网络中的传播分析[J];计算机工程;2011年10期

3 孙鑫;刘衍珩;朱建启;李飞鹏;;社交网络蠕虫仿真建模研究[J];计算机学报;2011年07期

4 亓开元;赵卓峰;房俊;马强;;针对高速数据流的大规模数据实时处理方法[J];计算机学报;2012年03期

5 金澈清,钱卫宁,周傲英;流数据分析与管理综述[J];软件学报;2004年08期

6 张冬冬;李建中;王伟平;郭龙江;;数据流历史数据的存储与聚集查询处理算法[J];软件学报;2005年12期

7 王跃武;荆继武;向继;刘琦;;拓扑相关蠕虫仿真分析[J];软件学报;2008年06期

8 胡晨骏;王晓蔚;;基于多核集群系统的并行编程模型的研究[J];计算机技术与发展;2008年04期

9 ;Local and global approaches of affinity propagation clustering for large scale data[J];Journal of Zhejiang University(Science A:An International Applied Physics & Engineering Journal);2008年10期

【相似文献】

相关期刊论文 前10条

1 王红梅,朱洪秀,郑虹;一种改进的起泡排序算法及其性能分析[J];延边大学学报(自然科学版);2001年04期

2 朱建莉,刘宏强;常用排序算法综述[J];胜利油田师范专科学校学报;2002年04期

3 周海岩,郝保树;一种新的桶分配链接排序算法[J];太原师范专科学校学报;2002年01期

4 赵忠孝;基于概率分布的排序算法(1)[J];计算机工程与应用;2002年11期

5 赵忠孝;基于概率分布的排序算法(2)[J];计算机工程与应用;2002年12期

6 何文明;针对任意分布数据的高效分档混合排序算法[J];计算机工程与应用;2003年22期

7 尤志强,张大方;数据等概率分档排序算法有效性的定量研究[J];计算机学报;2003年01期

8 穆炯,蒲海波;对按位分段排序算法的研究[J];四川农业大学学报;2004年01期

9 李井润;一种基于统计的分段排序算法[J];微计算机应用;2004年03期

10 曹清录,王念平,张斌;合并排序算法的平均情形复杂性分析及其应用[J];计算机工程;2004年21期

相关会议论文 前10条

1 周晓方;金志权;;寻找最佳分布式排序算法[A];第九届全国数据库学术会议论文集(上)[C];1990年

2 张艳秋;李建中;;一种基于蛇型磁带的排序算法[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

3 刘春阳;叶君峰;母海龙;陆秋霞;陈沧;高莺;;一种商品标题主题词的重要性排序算法[A];第五届全国信息检索学术会议论文集[C];2009年

4 于芳;王大玲;于戈;陈冬玲;鲍玉斌;;面向用户的排序算法研究[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

5 王少帅;汤庆新;姚路;;并行独立集排序算法的改进与实现[A];第十六届全国青年通信学术会议论文集（上）[C];2011年

6 闫泼;马军;陈竹敏;;面向主题的网页排序算法研究[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年

7 张健沛;李连江;杨静;;个性化搜索引擎排序算法的研究与改进[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年

8 吴志彬;陈义华;;ANP中超矩阵排序算法研究[A];2006中国控制与决策学术年会论文集[C];2006年

9 陈丛丛;石冰;陈健;;面向主题的查询相关网页排序算法[A];第三届中国智能计算大会论文集[C];2009年

10 齐曼;张珩;;实时视觉仿真中帧连贯性应用[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年

相关重要报纸文章 前1条

1 广东 黄陀;基本算法简介（三）[N];电脑报;2001年

相关博士学位论文 前3条

1 赵立军;基于归并的高效排序算法的研究[D];中国科学院研究生院（计算技术研究所）;1998年

2 崔筠;无向基因组的移位排序算法[D];山东大学;2006年

3 郝凡昌;有向基因组复合操作重组排序算法研究[D];山东大学;2011年

相关硕士学位论文 前10条

1 王靖;数据库管理系统中高能效排序算法[D];浙江工业大学;2012年

2 尹晓;基因组移位排序算法的改进和评测[D];山东大学;2006年

3 黄兴;比特位拆分索引排序算法研究[D];清华大学;2007年

4 Mushtaq AbdulMutalib Hasson;一种论文时间与引用兼顾的科研论文排序算法[D];华中科技大学;2012年

5 刘声田;基于第一降序小队翻转排序算法的设计与实现[D];山东大学;2006年

6 曹臻;基于粗糙集的粒度排序算法[D];上海海事大学;2007年

7 侯红梅;图像搜索重排序算法研究[D];山东大学;2014年

8 徐艳霞;面向数学搜索的排序算法研究[D];兰州大学;2012年

9 张建英;稀疏正则化最小二乘排序算法[D];湖北大学;2011年

10 廉洁;改进的内容分析排序算法在搜索引擎中的研究与应用[D];大连交通大学;2013年

，

本文编号：2034082