基于二维划分的杰卡德相似系数批量计算效率优化

随着互联网用户及内容的指数级增长,大规模数据场景下的杰卡德相似系数计算对算法的效率提出了更高的要求。为提高算法的执行效率,对MapReduce架构下的算法执行缺陷进行了分析,结合Spark适用于迭代型及交互型任务的特点,基于二维划分算法将算法从MapReduce平台移植到Spark平台;并通过参数调整、内存优化等方法进一步提高了算法的执行效率。两组数据集分别在3组不同规模的集群上的实验结果表明,与MapReduce相比,Spark平台下的算法执行效率提高了4倍以上,能耗效率提升了3倍以上。     

基于Spark的ItemBased推荐算法性能优化

MapReduce计算场景下,复杂的大数据挖掘类算法通常需要多个MapReduce作业协作完成,但多个作业之间严重的冗余磁盘读写及重复的资源申请操作,使得算法的性能严重降低。为提高ItemBased推荐算法的计算效率,首先对MapReduce平台下ItemBased协同过滤算法存在的性能问题进行了分析;在此基础上利用Spark迭代计算及内存计算上的优势提高算法的执行效率,并实现了基于Spark平台的ItemBased推荐算法。实验结果表明：当集群节点规模分别为10与20时,算法在Spark中的运行时间分别只有MapReduce中的25.6%及30.8%,Spark平台下的算法相比MapReduce平台,执行效率整体提高3倍以上。     

一种优化MapReduce系统能耗的数据布局算法

在云计算技术和大数据技术的推动下,IT资源的规模不断扩大,其能耗问题日益显著.研究表明:节点资源利用率不高、资源空闲导致的能源浪费,是目前大规模分布式系统的主要问题之一.研究了MapReduce系统的能耗优化.传统的基于软件技术的能耗优化方法多采用负载集中和节点开关算法,但由于MapReduce任务的特点,集群节点不仅要完成运算,还需要存储数据,因此,传统方法难以应用到MapReduce集群.提出了良好的数据布局可以优化集群能耗.基于此,首先定义了数据布局的能耗优化目标,并提出相应的数据布局算法;接着,从理论上证明该算法能够实现数据布局的能耗优化目标;最后,在异构集群中部署3种数据布局不同的MapReduce系统,通过对比三者在执行CPU密集型、I/O密集型和交互型这3种典型运算时的集群能耗,验证了所提出的数据布局算法的能耗优化效果.理论和实验结果均表明,所提出的布局算法能够有效地降低MapReduce集群的能耗.上述工作都将促进高能耗计算和大数据分析的应用.     

基于Spark的FP_Growth算法的并行与优化

PFP_Growth算法是FP_Growth算法在Hadoop平台上基于MapReduce的并行化,该算法在分组过程中没有考虑负载均衡问题,导致各个节点完成任务时间不一致,甚至相差很大,从而降低了算法的执行效率。为了提高算法的执行效率,提出了一种基于Spark的RPFP算法,该算法对PFP_Growth算法在均衡分组和降低时间复杂度两方面进行优化,通过把负载大的项放在负载总和最小的组里面实现均衡分组,通过在链头表结构中加入一张哈希表达到快速访问元素地址的目的,从而降低时间复杂度。实验结果表明,RPFP通过优化PFP算法,有效提高了频繁项集的挖掘效率。     

基于Spark的并行频繁项集挖掘算法

关联规则挖掘是数据挖掘领域的重要研究方向之一。频繁项集的挖掘是关联规则挖掘的第一步,也是最重要的步骤。FP-Growth(Frequent Pattern-Growth)算法因其挖掘效率以及空间复杂度方面的优势被广泛应用于频繁项集挖掘任务中。面对海量数据,FP-Growth算法挖掘效率变得极低甚至失效。在Hadoop大数据平台上实现的基于MapReduce框架的并行FP-Growth算法——PFP算法解决在处理大规模数据时传统算法失效的问题,但是由于其将每次执行之后的中间结果输出到磁盘,降低算法执行效率。为提高并行FP-Growth算法执行效率,提出一种基于Spark的SPFPG算法。该算法运用负载均衡思想对分组策略进行改进,综合考虑分区计算量和FP-Tree规模两个因素,保证每个组之间负载总和近似相等。在Spark上实现FP-Growth算法——SFPG算法的基础上,实现优化后的SPFPG算法。实验结果表明,SPFPG算法相比SFPG算法挖掘效率更高,且算法具有良好的扩展性。     

基于作业历史运行信息的MapReduce能耗预测模型

在数据量规模剧增的背景下,大数据处理过程中产生的高能耗问题亟待解决,而能耗模型是研究提高能耗效率方法的基础。利用传统的能耗模型计算MapReduce作业执行能耗面临诸多挑战,在对大数据计算模型MapReduce的集群结构、作业的任务分解及任务与资源映射模型分析建模的基础上,提出基于作业历史运行信息的MapReduce能耗预测模型。通过对不同作业历史运行信息的分析,得到DataNode运行不同任务时的计算能力及能耗特性,继而实现在MapReduce作业执行前对作业能耗的预测。实验结果验证了能耗预测模型的可行性,并通过对能耗预测准确率调节因子的修正,能够达到提高能耗模型的预测准确度的目的。     

基于Hadoop平台协同过滤推荐算法

针对协同过滤推荐算法在数据稀疏性及在大数据规模下系统可扩展性的两个问题, 在分析研究Hadoop分布式平台与协同过滤推荐算法后, 提出了一种基于Hadoop平台实现协同过滤推荐算法的优化方案. 实验证明, 在Hadoop平台上通过MapReduce结合Hbase数据库实现算法, 能够有效地提高协同过滤推荐算法在大数据规模下的执行效率, 从而能够进一步地搭建低成本高性能、动态扩展的分布式推荐引擎.     

多MapReduce作业协同下的大数据挖掘类算法资源效率优化

由于任意的MapReduce作业都需要独立地进行任务调度、资源分配等一系列复杂的操作,这使得同一算法协同的多个MapReduce作业之间,存在着大量的冗余磁盘I/O及资源重复申请操作,导致计算过程中资源利用效率低下。大数据挖掘类算法通常被切分成多个MapReduce job协作完成。以ItemBased算法为例,对多MapReduce作业协同下的大数据挖掘算法存在的资源效率问题进行了分析,提出基于DistributedCache的ItemBased算法,利用DistributedCache将多个MapReduce job之间的I/O数据进行缓存处理,打破作业之间独立性的缺陷,减少map与reduce任务之间的等待时延。实验结果表明,DistributedCache能够提高MapReduce作业的数据读取速度,利用DistributedCache重构后的算法极大地减少了map与reduce任务之间的等待时延,资源效率提高3倍以上。     

基于Spark的序列数据质量评价

随着序列数据在实际中的广泛应用,序列数据质量评价成为学术、工业等众多领域的热门研究问题。目前主流的序列数据质量评价方法是基于概率后缀树模型进行数据质量评价,然而这种方法难以实现对大规模数据的处理。为解决此问题,提出了基于Spark的序列数据质量评价算法STALK(sequential data quality evaluation with Spark),并且采用了改进的剪枝策略来提高算法效率。具体地,在Spark平台下,利用大规模序列数据高效建立生成模型,并根据生成模型对查询序列的数据质量进行快速评价。最后通过真实序列数据集验证了STALK算法的有效性、执行效率和可扩展性。     

基于Spark的极限学习机算法并行化研究

极限学习机算法虽然训练速度较快,但包含了大量矩阵运算,因此其在面对大数据量时,处理效率依然缓慢。在充分研究Spark分布式数据集并行计算机制的基础上,设计了核心环节矩阵乘法的并行计算方案,并对基于Spark的极限学习机并行化算法进行了设计与实现。为方便性能比较,同时实现了基于Hadoop MapReduce的极限学习机并行化算法。实验结果表明,基于Spark的极限学习机并行化算法相比于Hadoop MapReduce版本的运行时间明显缩短,而且若处理数据量越大,Spark在效率方面的优势就越明显。     

Investigating the performance of Hadoop and Spark platforms on machine learning algorithms

One of the most challenging issues in the big data research area is the inability to process a large volume of information in a reasonable time. Hadoop and Spark are two frameworks for distributed data processing. Hadoop is a very popular and general platform for big data processing. Because of the in-memory programming model, Spark as an open-source framework is suitable for processing iterative algorithms. In this paper, Hadoop and Spark frameworks, the big data processing platforms, are evaluated and compared in terms of runtime, memory and network usage, and central processor efficiency. Hence, the K-nearest neighbor (KNN) algorithm is implemented on datasets with different sizes within both Hadoop and Spark frameworks. The results show that the runtime of the KNN algorithm implemented on Spark is 4 to 4.5 times faster than Hadoop. Evaluations show that Hadoop uses more sources, including central processor and network. It is concluded that the CPU in Spark is more effective than Hadoop. On the other hand, the memory usage in Hadoop is less than Spark.

     

云计算中Hadoop技术研究与应用综述

Hadoop作为当今云计算与大数据时代背景下最热门的技术之一,其相关生态圈与Spark技术的结合一同影响着学术发展和商业模式。首先介绍了Hadoop的起源和优势,阐明相关技术原理,如MapReduce,HDFS,YARN,Spark等;然后着重分析了当前Hadoop学术研究成果,从MapReduce算法的改进与创新、HDFS技术的优化与创新、二次开发与其它技术相结合、应用领域创新与实践4个方面进行总结,并简述了国内外应用现状。而Hadoop与Spark结合是未来的趋势,最后展望了Hadoop未来研究的发展方向和亟需解决的问题。     

云平台下图数据处理技术

针对Hadoop云平台下MapReduce计算模型在处理图数据时效率低下的问题,提出了一种类似谷歌Pregel的图数据处理计算框架--MyBSP.首先,分析了MapReduce的运行机制及不足之处;其次,阐述了MyBSP框架的结构、工作流程及主要接口;最后,在分析PageRank图处理算法原理的基础上,设计并实现了基于MyBSP框架的PageRank算法.实验结果表明,基于MyBSP框架的图数据处理算法与基于MapReduce的算法相比,迭代处理的性能提升了1.9~3倍.MyBSP算法的执行时间减少了67%,能够满足图数据高效处理的应用前景.     

适于进化算法的迭代式MapReduce框架

MapReduce模块化的编程大大降低了分布式算法的实现难度,但同时也限制了它的应用范围。介绍了MapReduce的基本结构及其实现迭代算法的缺陷,并针对基于MapReduce进化算法效率低下的问题,在对MapReduce的计算框架进行研究的基础上提出了一种适用于进化算法的迭代式MapReduce计算框架。描述了迭代式MapReduce计算框架的实现需求及其具体实现,提出并证明了异常机制的可行性,且在公有的Hadoop云计算平台上对提出的框架进行了验证。实验结果表明,基于迭代式MapReduce计算框架的并行遗传算法在算法的加速比上与基于MapReduce的并行遗传算法相比有较大的提高。     

三角形的并行枚举算法

经典GT算法是三角形并行枚举算法的MapReduce实现,然而该算法只能枚举全图的三角形结构,对部分顶点构成的三角形结构无法直接进行枚举。针对此问题,提出一种直接枚举部分顶点构成三角形结构的并行算法。首先,通过分析被选点的分布,给出被选点构成三角形的所有组合集合;然后,通过对该集合的筛选,实现对部分点构成三角形结构的直接枚举;最后,将该算法在Spark系统实现,以实现该算法的高效性和广泛性。在人工生成数据集和真实数据集上与GT算法进行对比实验,实验结果表明,所提改进算法的运行时间只有GT算法运行时间的1/3,在Spark上的运行时间仅是Hadoop上运行时间的1/7。该算法可用于更高效地直接生成图中任意点所构成的三角形数据集。     

Flame-MR: An event-driven architecture for MapReduce applications

Nowadays, many organizations analyze their data with the MapReduce paradigm, most of them using the popular Apache Hadoop framework. As the data size managed by MapReduce applications is steadily increasing, the need for improving the Hadoop performance also grows. Existing modifications of Hadoop (e.g., Mellanox Unstructured Data Accelerator) attempt to improve performance by changing some of its underlying subsystems. However, they are not always capable to cope with all its performance bottlenecks or they hinder its portability. Furthermore, new frameworks like Apache Spark or DataMPI can achieve good performance improvements, but they do not keep compatibility with existing MapReduce applications. This paper proposes Flame-MR, a new event-driven MapReduce architecture that increases Hadoop performance by avoiding memory copies and pipelining data movements, without modifying the source code of the applications. The performance evaluation on two representative systems (an HPC cluster and a public cloud platform) has shown experimental evidence of significant performance increases, reducing the execution time by up to 54% on the Amazon EC2 cloud.     

基于Hadoop的协同过滤并行化算法

在针对大数据的迅速增长,为了改善协同过滤算法的推荐效率,使得推荐精度越来越高,提出基于Hadoop平台的协同过滤并行化算法,将传统的基于用户的协同过滤在Hadoop平台下进行MapReduce编程模型,实现并行化.通过利用MovieLens公用数据集对改进前后的算法对比,验证了并行化的协同过滤效率更高,也更加适合大规模数据的推荐.     

基于MapReduce虚拟集群的能耗优化算法

随着全球能源危机的出现,许多研究者开始关注数据中心的能耗问题。在满足用户需求的前提下,减少数据中心的活跃节点个数能够有效地降低其能耗。传统的减少活跃节点的方式是虚拟机迁移,但虚拟机迁移会造成极大的系统开销。提出一种基于MapReduce虚拟集群的能耗优化算法--在线时间平衡算法OTBA,能够减少活跃物理节点数,有效降低数据中心的能耗,并且避免了虚拟机的迁移。通过建立云数据中心的能耗模型、用户提交服务的排队模型和评价作业完成质量的作业运行模型,确定了数据中心节能模型的目标函数和变量因子。在线时间平衡算法是基于虚拟云环境和在线MapReduce作业的一种节能调度算法,能够在虚拟机的生命周期和资源利用率之间做出权衡,使数据中心激活的服务器达到最少,能耗降到最低。此外,该结果通过仿真和Hadoop平台上的实验得到了验证。