一种基于MapReduce的关联规则挖掘算法

本文从减少I/O时间的角度出发,结合云计算Hadoop平台的Map Reduce模型,提出了一种基于Map Reduce的关联规则挖掘算法.算法采用幂集计算候选项集,采用Map Reduce模型在多个节点上并行找出所有频繁项集,只需要扫描事务数据库1次.实验结果表明：在事务的平均项长较小的情况下,算法具有很好的加速比和数据规模增长性.     

基于MapReduce的两表数据倾斜连接的优化算法

针对Range partition算法不能优化数据集严重倾斜情形下的两表连接效率问题, 提出一种改进的数据倾斜连接算法. 该算法将倾斜数据和非倾斜数据区别处理, 利用复制、 广播方法将数据发送到每个Reduce节点, 通过一轮Map/Reduce任务完成所有的连接操作, 可有效均衡每个Reduce处理量, 解决了数据严重倾斜对两表连接性能的影响. 与传统的分区连接算法比较结果表明, 该算法有效.     

基于聚类蚁群算法的虚拟机资源分配算法研究

深入分析云计算环境下虚拟机资源调度分配的调度结构及与之对应的调度策略和算法后,结合云计算资源分配的最新研究成果和发展趋势,研究出一种基于聚类算法和蚁群算法的虚拟机资源分配算法.该算法基于Map/Reduce框架提出,着眼于如何为众多不同的用户任务分配虚拟机节点,充分考虑云计算环境中物理机的地域差异.在一个物理机区域内寻找分配虚拟机资源时引入蚁群算法,能更好地确保用户任务的按时完成,任务执行时间跨度方面满足服务等级协议(SLA).     

Item-Based并行协同过滤推荐算法的设计与实现

基于协同过滤的推荐已成为推荐系统中广泛采用的推荐技术.由于应用中用户数目和商品条目的日益增长,在计算相似度和计算预测时,单机集中式计算已不能满足推荐系统实时性和可扩展性的要求.针对这一问题,设计并实现了Item-Based并行协同过滤推荐算法.该算法采用Hadoop的MapReduce与HDFS架构,可分为Map与Reduce两个过程.通过在Map和Reduce节点上的并行处理可提高算法的执行效率.实验结果表明,该算法可明显减少推荐时间,提高推荐实时性,获得良好的可扩展性.     

一种基于Map Reduce的关联规则挖掘算法

提出了一种基于Map Reduce模型的Apriori改进算法,该算法利用Map Reduce模型分布式处理海量的输入数据,结合Apriori算法,得到局部频繁项集,通过聚合处理得到全局频繁项集.实验证明,该算法是有效的.     

面向云环境的蛋白质折叠模拟计算并行化算法

提出了面向云环境Yarn(yet another resource negotiator)规范的蛋白质折叠模拟计算并行化算法Yarn_PERM。分析了蛋白质折叠的格点模型PERM算法的运行流程及其面向MapReduce的子任务划分方式。Yarn_PERM算法实现采用Hadoop2.0的Yarn框架作为工作平台,其资源的分配与调度、应用子任务的申请和子任务的具体执行都由Yarn来透明地完成;描述了Yarn_PERM算法的Map程序与Reduce程序及主控程序的功能实现。实验结果表明:在相同的时间内Yarn_PERM比PERM串行计算、MapReduce的PERM计算在能量最低寻优的吞吐量上明显增加,加速比和可扩展性上也有明显的优势。     

面向Yarn规范的蛋白质折叠模拟计算并行化算法

为了提高生物信息学中蛋白质折叠模拟计算的速度,提出了面向Yarn(Yet Another Resource Negotiator)规范的蛋白质折叠模拟计算并行化算法Yarn_PERM。分析了蛋白质折叠的格点模型PERM算法的运行流程及其面向Map-Reduce的子任务划分方式。Yarn_PERM算法实现采用Hadoop2.0的Yarn框架作为工作平台,其资源的分配与调度、应用子任务的申请和子任务的具体执行都由Yarn来透明的完成;描述了Yarn_PERM算法的Map程序与Reduce程序及主控程序的功能实现。选择了一个有代表性的蛋白质序列数据作为案例程序进行了测试。实验结果表明：在相同的时间内Yarn_PERM比PERM串行计算、Map-Reduce的PERMS计算在能量最低寻优的吞吐量上明显增加,加速比和可扩展性上也有明显的优势。     

一种多策略要素的数据访问调度算法

考虑到任务的重要性、截止时间和资源分布等因素,设计了一种多策略要素的调度算法(MPES),以解决不完全独立的多源分布式气象水文数据库的访问控制问题.该算法为不同优先级的任务设定不同调度窗口,并对节点的安全级别、内容属性和负荷情况进行匹配判定,选择最佳服务节点,以优化系统公平性和整体效率.MPES算法根据队列优先级和可利用的服务资源,动态计算和调整调度窗口;优先级越高的队列,调度窗口越大,意味着可被服务的任务越多.在每个队列调度窗口时间内的任务被轮流执行.对于同一队列中的任务,根据最小松弛度优先调度策略,决定其进入调度窗口的次序,保证接近截止期的任务先执行.仿真试验结果表明,在不同的网络负荷下,MPES算法得到的分布式数据库访问任务的服务效率和公平性较MCT算法和Min-Min算法均有明显提高,尤其是高负荷情况下,总服务时间减少了11.4％ ～12.3％.     

动态在线Map/Reduce流数据处理模型及作业拓扑管理协议

针对海量流数据的在线处理需求,提出一种不同于传统Map/Reduce流数据处理的系统模型Flexible workflow.该模型对workflow处理单元进行在线Map/Reduce并行化,实现了SPATE系统;同时为该系统定义一组关于作业的建立、管理和维护的通信规程,即拓扑管理协议.SPATE系统解决了在线Map/Reduce流数据处理过程中要求实时性及可扩展性的问题.实验验证了拓扑管理协议的有效性,拓扑管理协议能有效管理Flexible workflow流数据处理模型.     

无线传感器网络中任务调度算法的研究

近几年,无线传感器网络能够实时监测和传输环境数据信息变得日益重要,尤其在民用和军事领域得到很广泛的应用.无线传感器网络具有传统网络无可比拟的优势,每个传感器节点用来感知周围环境事件和采集数据,并将采集的数据通过一跳或者多跳路由传给簇头节点或者接收器节点,然后发送到基站或数据中心进行处理.假定每个节点对信息的处理看作是一个任务,考虑节点能量限制,节点采用唤醒/休眠机制,在唤醒期间确保节点任务完成,簇头节点能够调度处理多个传感器节点的任务.文中解决的问题:在满足多个传感器节点任务处理的截止期失效前,簇头节点如何合理的调度任务,提出了改进的 RM(rate-monotonic) 调度算法和动态的抢占式最早截止期优先任务调度算法 (Preemptive Earliest Deadline First Algorithm,PEDFA).通过具体任务实例说明算法的实现过程,结果表明该算法运行简单,能够很好减少节点任务的延迟时间,实现节点任务的合理调度.     

数据密集型计算环境下离群点挖掘算法设计与实现

在数据密集型计算环境中,数据具有海量、高速变化、分布存储和异构等特征,对数据挖掘算法的设计与实现提出了新的挑战.基于MapReduce模型,提出了一种网格技术与基于LOF方法相结合的离群点挖掘算法MR_LOF.Map阶段采用网格进行数据约简,将代表点信息发送给主节点;Reduce阶段使用基于密度的离群点挖掘算法,借助网格期望值E筛选出稠密区域.该算法只需计算稀疏区域对象的LOF值,降低了算法的时间复杂度.实验结果表明,在数据密集型计算环境中,该方法能有效的对离群点进行挖掘.     

MR-IDPSO: A Novel Algorithm for Large-Scale Dynamic Service Composition

In the era of big data, data intensive applications have posed new challenges to the field of service composition. How to select the optimal composited service from thousands of functionally equivalent services but different Quality of Service(Qo S) attributes has become a hot research in service computing. As a consequence,in this paper, we propose a novel algorithm MR-IDPSO(Map Reduce based on Improved Discrete Particle Swarm Optimization), which makes use of the improved discrete Particle Swarm Optimization(PSO) with the Map Reduce to solve large-scale dynamic service composition. Experiments show that our algorithm outperforms the parallel genetic algorithm in terms of solution quality and is efficient for large-scale dynamic service composition. In addition,the experimental results also demonstrate that the performance of MR-IDPSO becomes more better with increasing number of candidate services.     

Hadoop性能优化研究

优化Hadoop的性能可大大提高Map Reduce的工作效率,缩短任务执行时间,增加分布式计算的吞吐量.Hadoop的执行性能受到多种配置属性的影响,不同配置属性间也存在相互制约关系.基于遗传算法,对配置方案不断选择、交叉、变异,多次迭代后产生近似最优配置方案.实验结果表明该配置方案能够有效提高系统性能,并且具有稳定性和适用性.     

基于异构模式的云计算关键技术研究

结合云计算中Map/Reduce分布式编程技术引入了基于CPU-GPU异构混合并行编程模式,给出了该并行编程模式的原理和实现过程。该模式通过采用CUDA多线程并行机制提高了大规模数据处理的效率。文中对比分析了云计算中两种典型的分布式存储系统GFS和HDFS,最后从宏观角度阐释了云计算虚拟化技术的三层部署架构和基本类型。     

云环境下的流式空间信息服务

随着物联网、传感器技术与应用的发展,对大规模多维空间数据集成与服务的需求愈加迫切.如何实现基于大规模、多维空间数据流的实时计算成为空间数据处理领域的难点.结合云计算的特点,提出针对高速、大流量空间数据的实时处理方法.通过对多维、异构空间数据进行智能处理,生成结构化、简洁化的中间属性集;利用针对高速数据流的大规模数据实时处理方法,解决Map/Reduce难以满足此类计算实时性要求的不足.在此基础上,设计了流式空间信息组织模型与云端适配方法,对方法中的关键技术问题进行了描述.实践表明,该方法可显著提高动态空间信息的服务质量与运行性能.     

基于Map/Reduce的网页消重并行算法

网页消重模块是搜索引擎系统的重要组成部分,其作用是对搜索引擎的爬虫系统下载的网页进行过滤,去除重复内容的网页,从而提高搜索引擎爬虫系统的性能和检索的质量。提出了一种网页消重的并行算法以及基于Map/Reduce的实现机制,并通过实际网站的实验验证了该消重算法的稳定性和处理大量网页时的并行性能。     

基于MapRedue的大规模矢量空间数据选择查询处理

为高效地处理大规模矢量空间数据,基于Hadoop的并行计算框架MapRedue,实现了一种分布式的矢量空间数据选择查询处理方法.首先,分析OGC简单要素标准与Hadoop的Key/Value数据模型,设计了可存储于Hadoop HDFS的矢量文件格式;其次,根据两阶段的过滤-精炼策略,对Map输入数据分片、选择查询处理过程及Reduce结果合并等关键步骤进行了详细阐述;最后,基于上述技术,利用Hadoop集群环境对所提出的方法进行验证,该方法具有较好的可行性和较高的效率.