MapReduce模型下的并行线性时间选择算法研究  

Research on parallel liner time selection algorithm on MapReduce model

作　　者：王永贵[1] 李鸿绪 宋晓[1] 

机构地区：[1]辽宁工程技术大学软件学院,辽宁葫芦岛125105

出　　处：《计算机工程与设计》2014年第4期1242-1246,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(60903082);辽宁省教育厅基金项目(L2012113)

摘　　要：针对线性时间选择算法随着元素数量的增加,执行效率较低的缺点,提出了MapReduce模型下的并行线性时间选择算法。重新设计了线性时间选择问题的算法,使其符合以key/value数据形式作为输入的MapReduce编程模型。并行计算局部最优解,汇总局部最优解再计算出全局最优解。实验结果表明,在面对大数据情况下,经过改进后的MapReduce模型下的并行线性时间选择算法具有执行效率高,且执行效率随着并行程度的增加而提高的特点。The execution efficiency of liner time selection algorithm is relatively low with the increased amount of element. A parallel liner time selection algorithm on mapreduce is proposed. The liner time selection algorithm is redesigned to meet the ma- preduce programming model which puts key/value form asits data input. The locally optimal solution is computed in parallel. The locally optimal solution is sunmaaried and the globally optimal solution is gotten. Experiments show that the parallel liner time selection algorithm on mapreduce is with high performance in the face of big data. And the execution efficiency of the algo- rithm is high with more compute units.

关 键 词：并行计算 MAPREDUCE模型 线性时间选择算法 局部最优解 全局最优解 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]