摘要：为使链路预测应用于大型复杂网络,设计并实现了一种基于mapreduce计算模型的并行链路预测算法,包含了9种基于局部信息的相似性指标,在稀疏网络上的时间复杂度为O(N).首先,在公共数据集上验证了并行算法的有效性,随着抽取因子的增加,召回率升高而准确率下降.在不同类型的10个大规模复杂网络数据集上的实验结果表明,基于mapreduce计算模型的并行链路预测算法比传统算法具有更高的效率,算法的运行时间随着并行程度的增加而下降.提出并证明了AUC(area under a receiver operating characteristic curve)评价指标的上下界,实验表明,上下界的中值和实际AUC值很接近,并且AUC评价指标侧重于预测分数值是否为0而不是分数值的大小.在网络拓扑性质中,平均聚集系数对AUC值的影响最大,并且AUC值随着网络平均聚集系数的增加而提高.

摘要：mapreduce作业性能与内存配置存在极大的相关性,针对准确预测作业内存困难问题,根据Java虚拟机(JVM)的分代内存管理特点,提出了一种分代内存预测方法.首先使用回归模型对年轻代与垃圾回收平均时间的关系进行建模,将寻找合理年轻代内存大小的问题转换为一个受约束的非线性优化问题,并设计搜索算法来求解该优化问题.文中还建立mapreduce作业的Map任务和Reduce任务性能与内存的关系模型,求解最佳性能的内存需求,从而获得Map任务和Reduce任务的年长代内存大小;使用聚类算法预测JVM晋升对象阈值,优化JVM配置,减少了JVM的垃圾回收暂停时间.实验结果表明,文中提出的方法能准确预测作业的内存需求,显著提升作业运行性能.

摘要：综述了近年来基于mapreduce编程模型的大数据处理平台与算法的研究进展.首先介绍了12个典型的基于mapreduce的大数据处理平台,分析对比它们的实现原理和适用场景,抽象其共性;随后介绍基于mapreduce的大数据分析算法,包括搜索算法、数据清洗/变换算法、聚集算法、连接算法、排序算法、偏好查询、最优化算法、图算法、数据挖掘算法,将这些算法按照mapreduce实现方式分类,分析影响算法性能的因素;最后,将大数据处理算法抽象为外存算法,并对外存算法的特征加以梳理,提出了普适的外存算法性能优化方法的研究思路和问题,以供研究人员参考.具体包括优化外存算法的磁盘I/O、优化外存算法的局部性以及设计增量式迭代算法.现有的大数据处理平台和算法研究多集中在基于资源分配和任务调度的平台动态性能优化、特定算法并行化、特定算法性能优化等领域,所提出的外存算法性能优化属于静态优化方法,是现有研究的良好补充,为研究人员提供了广阔的研究空间.

摘要：为了解决原有单机空间数据库管理系统在存储能力、计算能力和可扩展能力上的不足,在分布式文件系统的基础上设计并实现了一种基于并行计算框架mapreduce的空间矢量数据管理系统Meadow,并重点讨论了利用mapreduce并行处理空间查询的数据分割方法、副本避免方法及关键算法的设计策略,最后给出了定量的分析和论证。实验表明,相对于单机Oracle Spatial,利用mapreduce并行处理空间查询的方法具有良好的性能和近似线性的加速比。实验结果也验证了mapreduce在诸如空间数据管理系统这种基于小规模集群的计算密集型应用中同样具有良好的性能。

摘要：研究一类基于mapreduce模型的两阶段平行机调度问题。该模型中的每个工件包含Map和Reduce两道工序,前一工序的任务可以划分并同步加工,而后一工序不可划分,结合工件的到达时间、交货时间等约束,以最大完工时间和总延迟时间的加权和作为优化目标构建混合整数规划模型,设计采用差分变异策略和逐维角度扰动机制的改进鲸鱼优化算法求解模型。数值仿真实验结果表明,所设计的算法相对于经典的鲸鱼优化算法、粒子群算法的求解效果有显著的提升,验证了模型和所设计算法的有效性。

摘要：针对现阶段大规模流数据在线处理的广泛需求,本文提出了弹性在线mapreduce流数据处理模型及相关的动态拓扑结构协议。该模型兼容现有mapreduce模型,采用内存计算模式,并具有动态的作业拓扑结构,支持大规模流数据处理作业在运行过程中的弹性调整,从而满足流数据的时效性、动态性和突发性等特殊要求。在弹性在线mapreduce模型的基础上建立了流数据处理作业动态拓扑结构管理机制,设计了作业在线初始化协议和在线调整协议。为进一步提高系统灵活性和整合资源,提出了作业间的操作共享概念,设计了作业共享协议。通过协议分析,本文提出的在线初始化协议、在线动态调整协议及作业共享协议的最大复杂度均为O(n);在数据流量发生突发性变化时,系统具有良好的可伸缩性。

摘要：研究了一类基于mapreduce模型的平行机调度问题.每个工件包含Map和Reduce两道加工工序,Map工序可以分割为若干个子任务,并且在多台平行机上同时并行加工,Reduce工序只有在该工件的所有Map工序的子任务加工完成后才能进行,而且Reduce只能在一台机器上加工且不可中断.结合工件具有释放时间和加工准备时间等约束,以最小化最大完工时间为目标,构建了混合整数规划模型,并设计了采用差分变异策略和逐维Levy扰动机制的改进正弦余弦算法来求解该模型.最后,利用数值仿真实验与标准正弦余弦算法及遗传算法进行对比,实验结果表明,运用改进正弦余弦算法求解的结果与下界值的平均相对偏差GAP为3.02%,较标准正弦余弦算法以及遗传算法的效果提升显著,显示了该改进算法的有效性.

摘要：大规模网络结构设计是构建大规模分布式系统和E级高性能计算集群的核心技术之一,底层网络设计者需要结合顶层应用通信流量特征,进行网络结构选型与优化.不当的应用通信模型会引起网络结构设计与实际需求的背离,进而导致系统通信和整体性能的下降.传统基于"黑盒"数据分析的流量建模方法存在业务建模粒度粗和应用数据规模扩展性差等缺陷.该研究引入模拟业务内部逻辑的"事件驱动"思想,提出一种针对主流计算模式mapreduce进行流量建模与流量产生方法.与真实应用流量的对比评测显示,该方法能够准确体现mapreduce计算业务所产生网络流量的特征.基于正确的流量模型,该文对四种主流数据中心网络进行了性能模拟分析.结果表明:相较负载随机均匀分布流量,同一种网络在负载mapreduce特性流量时性能将下降超过30%,因此特性流量能更加明显地展现网络拥塞与瓶颈问题.仿真实验所得到的有关网络性能瓶颈、拓扑可扩展性以及网络性价比的结论,为大规模数据中心网络选型和性能优化提供了新的依据.

摘要：随着语义网的快速发展,RDF语义数据大量涌现.大规模RDF语义数据推理的一个主要问题是计算量大、完成计算需要消耗很长的时间.显然,传统的单机语义推理引擎难以处理大规模的语义数据.另一方面,现有的基于mapreduce的大规模语义推理引擎,缺乏对算法在分布和并行计算环境下执行效率的优化,使得推理时间仍然较长.此外,现有的推理引擎大多存在可扩展性方面的不足,难以适应大规模语义数据的增长需求.针对现有的语义推理系统在执行效率和可扩展性方面的不足,文中提出了一种基于mapreduce的并行化语义推理算法和引擎YARM.为了实现分布和并行计算环境下的高效推理,YARM做出了以下4点优化:(1)采用合理的数据划分模型和并行化算法,降低计算节点间的通信开销;(2)优化推理规则的执行次序,提升了推理计算速度;(3)设计了简洁的去重策略,避免新增作业处理重复数据;(4)设计实现了一种新的基于mapreduce的并行化推理算法.实验结果表明,在真实数据集和大规模合成数据集上,YARM的执行速度比当前最新的基于mapreduce的推理引擎快10倍左右,同时YARM还表现出更好的数据和系统可扩展性.

摘要：单机运行环境难以满足基于海量数据的大图算法对时空开销的需求,如何设计高效的面向云计算环境的分布式大图算法越来越受到人们的关注,mapreduce作为云计算的核心计算模式受限于易并行(EP)计算模型的制约不易表达图算法.文中突破了mapreduce基于易并行计算的假设,增强了mapreduce既有的编程规范,新的大同步(BSP)计算模型既能保证兼容旧的mapreduce作业可以无改动的运行,同时引入消息传递机制允许变化的状态数据在并行任务的超级步间进行交互.系统提供高度灵活的消息自定义接口,针对不同应用需求设计了轻量级和重量级两种自适应的消息传递机制,更高效地支持有数据交互需求的包含迭代处理的一大类图算法.在真实大规模图数据集上的实验结果表明,相比于原始的mapreduce作业外部链式处理,该文提出的BSP模型下的内部超级步迭代计算模式大幅降低了大图算法的处理时间.