基于MapReduce的C-Cubing并行算法

封闭立方体计算的主要任务是在生成一个数据单元时,判断其是否封闭。针对该问题,C-Cubing是新近提出的一种有效的方法,不同以往基于输出或基于元组的方法,它仅通过特定的度量,即封闭性度量,就可以判断出封闭单元。然而随着数据量的增加,C-Cubing的性能下降,因此它的并行算法还有待研究。本文提出基于MapReduce并行框架,采用C-Cubing对封闭立方体并行计算的方法,并在Hadoop上给予了实现。实验结果表明,本方案能够利用廉价的PC机器,有效提高了在较大数据集上计算封闭立方体的性能。     

云环境中基于金字塔模型的影像数据存储方法

随着卫星遥感获取技术的发展,影像数据量呈几何式增长,传统数据存储技术已经无法适应海量影像数据的处理要求.结合金字塔模型和MapReduce架构提出了一种适用于云计算环境的分布式并行存储方法—BMLStorage(storage based on MapReduce and local file system),该方法基于金字塔模型对影像数据进行分层分块处理,并对所得瓦片重新编码.定义了一种新的存储规则,使得所有瓦片可以按照此规则利用Hadoop中的MapReduce框架实现并行存储.实验表明,该方法与现有方法相比,在海量影像数据存储性能方面有一定的提高.     

基于MapReduce的大规模图挖掘并行计算模型

在如何快速发现大规模网络的结构和特性问题中,网络规模及复杂度的快速增长给其分析研究带来了新的挑战.MapReduce及其开源实现Hadoop给大规模图的高效处理带来了希望.基于MapReduce框架的集群系统,提出了1种新的计算模型用于大规模图形的3-clique计算,来实现图挖掘.计算的基本步骤是:首先获取每个节点的第1跳信息,然后是第2跳信息,最后得到所有基于该节点的3-clique.该计算模型可以用来计算聚集系数,并且可以用于三大通话网络的挖掘.实验结果证明这种计算模型具有良好的可扩展性和性能.     

基于MapReduce的分布式期望最大化算法

利用MapReduce编程模型的简化性和期望最大化算法(Expectation maximization,EM)的高精度、恒收敛性,提出了一种对数据集规模无限制的数据处理算法;并通过对高斯混合模型的参数估计进行算法性能的测试。结果表明,算法能改善传统EM算法在处理大规模数据集时效率低的缺点,具有较好的加速比及可扩展性。     

MapReduce框架下的查询结果共享

当前的大规模数据分析通常在MapReduce框架下执行查询。由于MapReduce框架本身的冗余性以及查询之间的重叠性,复用已有查询的结果可以大幅提高查询的执行效率。复用查询的结果需要对其进行存储和匹配管理,产生高昂的系统开销,抵消复用的部分效果。本文针对目前先进的查询结果复用系统ReStore在管理查询结果和匹配中存在的效率低下的问题,提出森林结构的Job存储管理技术和与之相适应的匹配算法,提高查询的匹配效率,减少系统的开销。为了使系统能够充分复用已执行查询的结果,本文提出对多个查询进行预处理的方案,通过改变各查询进入Pig编译器进行编译的顺序,从而改变Job的执行顺序,使得加载相同数据集的Job同时执行,减少与存储库进行匹配的次数。实验表明：在构建存储结构与匹配已有结果过程中,本文提出的方法与ReStore相比,节约16.3%的时间开销,伸缩性也更好。     

面向大数据应用的多层次混合式并行方法

基于很多大数据应用存在对数据进行多种并行处理的需求, 提出两层混合式并行方法, 即执行单元的混合并行和计算模型的混合并行. 通过在同一个计算节点上执行单元的混合并行, 充分挖掘基础设施的计算能力, 从而提高数据处理性能; 采用在同一个执行引擎中集成多个计算模型的并行方法, 以适合应用多样异质处理模式. 不同的混合并行方法可以契合不同的数据和计算特点, 以满足不同的并行目标. 介绍了混合式并行方法的基本思想, 并以前期开发的并行编程模型BSPCloud为基础, 阐述了进程和线程混合并行、BSP和MapReduce混合并行的主要实现机制.     

基于哈希表的MapReduce算法优化

分布式并行计算是提高计算机性能常用的方法,但针对不同需求,并行程序的设计并没有统一的模型与方法,使得并行程序的编写完全依靠开发人员的经验。Google公司提出的分布式并行编程模型MapReduce能够完成特定类型的并行程序的开发与运行。使用哈希表对MapReduce分布式并行编程模型进行优化,减少中间结果中的碎片,并省略Combiner中间函数的调用,减少传输负载,提升运行效率,同时兼顾了Map函数与Reduce函数接口的属性,保持了MapReduce模型的并行性特点。     

基于MapReduce的合成孔径雷达后向投影快速成像方法

针对雷达大场景高分辨率高精度快速成像的应用需求,提出一种基于MapReduce的合成孔径雷达后向投影快速成像方法,将方位向成像任务划分成若干个成像单元,进行分布式并行化方位向成像计算,最后将所有成像单元的计算结果进行相参累加。该方法对每个脉冲数据标上天线阵元的位置信息,使得各个脉冲数据可以并行补偿相位;采用相等脉冲数划分成一个数据块的方式提高计算效率和实现负载均衡;设置Combiner函数对成像单元内的计算结果进行提前聚合,解决后期聚合时间较长的问题。实验验证了该方法的有效性,在保证成像准确的前提下,该方法的方位向成像在4台物理计算机搭建的分布式计算平台中进行,其计算速度是单机计算的后向投影方位向成像方法的3.7倍,可见该方法可以实现合成孔径雷达大场景高分辨率高精度快速成像。     

FP-Growth的并行加权关联规则挖掘算法

基于FP-Growth算法,提出一种并行加权的关联规则挖掘(PWARM)算法,证明其满足加权向下封闭性.使用MapReduce计算模型,在分布式集群中并行挖掘出关联规则.实验结果表明:该算法可以满足数据权重不同的需求,且在处理大数据集时能有效地提高挖掘的效率.     

Parallel bulk-loading of spatial data with MapReduce: An R-tree case

Current literature on parallel bulk-loading of R-tree index has the disadvantage that the quality of produced spatial index decrease considerably as the parallelism increases.To solve this problem,a novel method of bulk-loading spatial data using the popular MapReduce framework is proposed.MapReduce combines Hilbert curve and random sampling method to parallel partition and sort spatial data,thus it balances the number of spatial data in each partition.Then the bottom-up method is introduced to simplify and accelerate the sub-index construction in each partition.Three area metrics are used to test the quality of generated index under different partitions.The extensive experiments show that the generated R-trees have the similar quality with the generated R-tree using sequential bulk-loading method,while the execution time is reduced considerably by exploiting parallelism.