FSMBUS：一种基于Spark的大规模频繁子图挖掘算法

随着社交网络用户数的快速增加,大规模单图上频繁子图挖掘的需求越来越强烈.单机算法对大规模图的运行效率较低,难以支撑支持度较低的频繁子图的挖掘;现有的分布式环境下单图的频繁子图挖掘算法不支持子图增长模式的挖掘,它们所使用的Hadoop框架也不适合运行迭代式算法.提出了一种基于Spark的大规模单图频繁子图挖掘算法FSMBUS,通过次优树构建并行计算的候选子图,在给定最小支持度时挖掘出所有的频繁子图,并利用非频繁检测和搜索顺序选择实现优化,还设计了一种名为Sorted-Greedy的轻量级数据划分方法.实验结果表明,FSMBUS的效率要比现有单图上最新的算法快一个数量级,并支持更低最小支持度阈值以及更大规模图数据的挖掘,同时FSMBUS比其Hadoop的移植版要快2~4倍.     

基于Hadoop的大规模图像存储与检索

图像数据的指数型增长使得传统单机的图像检索在处理大规模图像时面临着检索速度慢、并发性差、检索准确率低的问题。由于图像特征文件都是小文件,本文提出将图像特征小文件进行适当的合并后存储于Hadoop的分布式文件系统HDFS中,实现大规模图像的快速存储和读取;为了适应大规模的图像检索,对图像Fisher向量进行二值化处理,并利用MapReduce并行编程模型实现基于二值Fisher向量和SIFT(Scale Invariant Feature Transform)特征的并行检索。在INRIA Holidays数据集、Kentucky数据集和Flicker1M数据集上的实验结果表明该方法扩展性强,能够取得较好的检索准确率,有效减少检索时间,提高检索速度,是一种高效的大规模图像存储和检索的方法。     

基于Hadoop平台的HITS算法

本文对Hadoop平台进行了分析研究后,与HITS算法的设计理论和技术相结合,对基于中文词汇网络的HITS算法进行了重新设计,使其符合Hadoop平台的框架,详细分析了Map／Reduce函数的设计方案．用测试数据在不同集群上做实验,实验结果证明,HITS算法在分布式环境下能很好的运行,集群的优越性明显．     

基于蚁群算法的Hadoop调度算法研究

为有效提高Hadoop集群作业调度的效率,提出一种基于蚁群算法的自适应作业调度的方案,有效利用蚁群算法正反馈的优势特点,使Hadoop作业调度器更高效地对任务进行分配,提高整体架构的作业性能。实验结果表明,该算法能够很好的平衡资源负载,减少任务的完成时间,提高系统处理任务的性能。     

Hadoop平台下一种改进蚂蚁算法的QoS路由研究

随着未来云计算的发展,各种云服务的应用将需要更高的网络性能。链路拥塞导致的数据包传输时延或数据包丢弃使得网络无法保障业务的QoS。目前普遍使用的链路状态路由算法不具有拥塞响应机制。本文通过在拥塞节点间发送连接蚂蚁寻找新路由来解决拥塞问题。NS2仿真结果表明,该算法能加快新的路由搜索,满足QoS的需求,并有效控制丢包率,时延等性能。     

一种Spark环境下的高效率大规模图数据处理机制

本文针对现有的图处理和图管理框架存在的效率低下以及数据存储结构等问题,提出了一种适合于大规模图数据处理机制。首先分析了目前的一些图处理模型以及图存储框架的优势与存在的不足。其次,通过对分布式计算的特性分析采取适合大规模图的分割算法、数据抽取的优化以及缓存、计算层与持久层结合机制三方面来设计本文的图数据处理框架。最后通过PageRank和SSSP算法来设计实验与MapReduce框架和采用HDFS作持久层的Spark框架做性能对比。实验证明本文提出的框架要比MapReduce框架快90倍,比采用HDFS作持久层的Spark框架快2倍,能够满足高效率图数据处理的应用前景。     

一种Hadoop中基于作业类别和截止时间的调度算法

Hadoop是一种开源可靠的分布式计算框架,而MapReduce是处理超大规模数据集的编程模型.鉴于Ha-doop内置的调度器不能很好地处理类别不同且有截止时间的作业的调度,提出了一种基于作业类别和截止时间的作业调度算法.作业分为CPU密集型和I/O密集型,并根据截止时间设置优先级来实现作业的调度.实验结果表明,该算法在充分利用集群的CPU和磁盘I/O的同时,能满足作业的截止期需求,当同一时间段内截止时间相近时算法达到最优,当某一队列中作业截止时间均比另一种队列短时,算法效率最低.     

SQM:基于Spark的大规模单图上的子图匹配算法

针对大规模数据图下基于回溯法的子图查询算法的准确率低、开销大等问题，为提高查询准确率，降低大图下的查询开销，提出一种基于Spark的子图匹配（SQM）算法。首先根据结构信息过滤数据图，再将查询图分割成基本查询单元；然后对每一个基本查询单元分别匹配后进行Join操作；最后运用并行化提高了算法的运行效率，减小了搜索空间。实验结果表明，与Stwig、TurboISO算法相比，SQM算法在保证查询结果不变的情况下，速度提高了50%。     

基于邻域的大规模图数据动态分割算法

随着图数据的规模日益增大,出现大量以动态图数据为基础的分布式处理需求,划分问题在动态图数据分布式处理领域尤为重要. 对大规模动态图数据上的划分问题进行研究,根据图结构性质及动态图特点,提出并实现基于邻域的动态图分割算法. 算法分为静态切分和动态调整两个阶段,其中基于割边算法整合现有最优化策略提出了大规模图数据的静态切割算法. 在优化后的静态切割算法的基础上,根据图数据的动态扩张的特性提出动态分割算法. 根据迁移顶点所达到的最小负载值进行顶点迁移,并在此基础上进行性能及割边控制优化操作. 最后,改进算法在各类图数据集上进行了验证,验证的结果显示在平衡度和割边等指标上优化后的算法效果显著,提高了划分的合理性,并且在保证割边不增加的情况下提高了图分割的平衡度.     

基于直径为2的摩尔图网络的并行矩阵乘算法

提出了一个并行矩阵乘算法IPBPMM(Interconnected Processor-Based Parallel Matrix Multiplication).该算法运行在以五角形、Petersen图和Hoffman-Singleton图等直径为2的摩尔图(满足n=d2+1,n为节点数,d为度)为拓扑结构的由n个独立处理器构成的机群并行计算环境中.与基于二维环绕网孔阵列拓扑结构的Cannon和Fox等并行矩阵乘法算法相比较,IPBPMM算法通信开销较小,加速比更高,同时还具有矩阵分块可随机分布在各个节点中,无需事先按一定规律装入各节点中的特点.同时IPBPMM算法也能很好地扩充到由多个直径为2的摩尔图为拓扑结构组合构成的并行计算环境中,且随着网络的扩大,算法的并行加速比更高.     

基于遗传算法的平面图画图算法

提出了一种基于遗传算法的新的平面图画图算法，算法将平面图画图问题转化为约束优化问题，用遗传算法求解目标函数的最优解的近似值，从而得到平面图的平面直线画法．新算法的优点是：方法简单，易于实现，画出的图形美观．实验结果表明：算法画出的图形要比文献[8]中的算法画出的图形美观，而其收敛性则要高于标准遗传算法．     

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

一个新的无向图画图算法

将一般无向图的画图问题转化为函数优化问题,用遗传算法求目标函数的最优解的近似值,从而得到无向图自动画图算法的一个一般框架.新方法的特点是:不同的画图算法的框架都一样,所不同的只是反映无向图画图问题的美观标准的目标函数.其优点在于,算法统一、方法简单、容易实现、便于修改,并且易于并行化,可以直接用来画非连通图.     

基于算法图的并行计算优化

研究基于算法图的并行计算优化设计方法。通过引入算法图，从数学机理上算法的并行结构进行描述，针对不同要求提出了对计算网络的并行优化设计方法，为设计并行算法提供了新的有途途径。     

一个基于DFS编码的图形匹配算法

快速有效的图形查询是图形数据库成功应用的关键。文章利用图的词典顺序，用唯一的最小DFS（深度优先搜索）编码表示每个图。根据两个图同构当且仅当它们的最小DFS编码相同这一性质，将图形匹配转化为图的最小DFS编码的比较：在判断两个标记图形是否同构时，可以先求出图的最小DFS编码，再用有效的匹配算法进行比较。     

基于最小生成树的图数据库索引算法

对复杂数据进行图模式建模近几年越来越流行,因此,在查询执行的优化过程中图索引技术变得至关重要.研究了图模式的索引问题,并且提出了一种近似的索引方法,称为MSTA方法.MSTA方法利用最小生成树结构作为索引特征,依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量,将最小生成树组织到一个称为MST树的索引结构中.MST树索引结构可以高效地支持多种查询,例如子图查询.MSTA方法具备高效的索引性能.在索引大小和索引建立时间方面,传统方法是MSTA方法的数十倍,甚至上百倍.MSTA方法虽然不能返回完整结果,但是可以返回经图距离度量排序最好的部分结果.     

基于顶点组重分配的动态增量图划分算法

图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上. 图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划分结果. 提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题. 在ED-IDGP算法中, 设计实时处理4种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量. 在ED-IDGP的局部优化器中, 利用基于改进标签传播算法的顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分区中做优化. 在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.     

基于特征索引的图相似查询过滤算法

分析图相似查询候选集的产生过程以及特征图之间的关系对候选图集的影响,提出一种基于特征索引的图相似查询过滤算法,使用GIndex算法建立特征图索引结构,通过特征图之间的选择性关系给出一个有序的特征集,并借助特征-图矩阵对数据库进行筛选得到候选图集。实验结果证明,该方法能准确地产生候选图集,从而提高图查询的效率。