一种存储介质优化的大规模图遍历方法研究

大图数据的BFS算法作为一种基础算法,受到工业界和学术界的广泛重视。不同平台涌现出众多大图BFS算法的研究工作,其中多使用固态硬盘来提高算法效率。在BFS算法遍历过程中,存储设备需要连续重复装载会数据以满足遍历需求,而数据重复装载造成大量数据擦写操作,严重影响了固态硬盘的使用寿命。由此可见,减少BFS算法数据擦写操作可以有效延长固态硬盘的使用寿命。结合图结构的特点,提出数据重用模型,用于描述图遍历过程中的数据重用程度;提出了基于图顶点度的启发式优先访问方法,该方法判断图顶点之间的独立性,并根据判断结果选择优先访问的图顶点,增加数据重用的可能性,提高缓存的命中率,减少闪存颗粒磨损。所提优化方法不修改BFS算法和大图数据,适用于各种BFS算法和数据集。最后,实验验证了所提数据重用模型的正确性,以及启发式优先访问方法的有效性。该优化方法应用于BFS-4K,B40C和Gunrock这3种常见的BFS算法上,能有效减少图遍历过程中的数据写入操作,固态硬盘的使用寿命可分别提高12%,15%,22%。

基于图遍历的局部社区发现算法

针对当前局部社区发现算法扩张速度慢不适用于大规模网络的问题,提出了一种基于图遍历的局部社区发现算法。该算法首先找出网络中度数最低的节点,以该节点为起点通过影响力函数将网络中的节点分为社区节点和边界节点,形成初步的社区划分,然后通过适应度函数确定边界节点的社区得到最终划分结果。实验结果表明,该算法在真实网络上进行测试时不仅能够有效地挖掘网络中的社区结构而且具有较快的速度。

基于全局图遍历的ST-GCN人体行为识别算法

传统的时空图卷积网络(spatio-temporal graph convolutional network, ST-GCN)模型存在诸多缺陷,如空间图构造受预定义影响、忽略非相邻节点间信息的有效利用以及计算成本过高等.针对上述问题,基于ST-GCN模型提出一种采用节点全局图遍历的自适应人体行为识别方法.通过建立节点关联函数找出初始节点,再遍历拓扑状态库找出变化较大的前条链路筛选关键连接特征;建立当前节点与相邻和非相邻节点间的有效关联,在卷积过程中增加位运算操作用于舍弃关联度较小的关节点,以期在减少计算量的同时通过直接捕捉人体节点间的位置和距离信息调整运动关联度,增强算法的自适应性.实验结果表明,该算法较原始ST-GCN模型的识别精度高2%,且计算成本低,每秒浮点运算次数下降2.9×10^(9).

基于全局图遍历的加权频繁模式研究

在以往的加权遍历模式应用过程中,挖掘是影响最终应用效果的主要问题。相比之下,在全局图遍历基础上加权频繁模式的应用能够有效解决挖掘问题。本文从图遍历分析入手,对基于全局图遍历的加权频繁模式进行研究和分析。

一种基于图遍历的本体分解方法

针对传统本体分解方法时间复杂度高的问题,给出了一种基于图遍历的本体分解方法。该方法通过查询引擎获取本体的三元组表示,即主体、谓词和客体,然后用RDF(资源描述框架)构建对应的本体图,图中节点对应主体和客体,边对应谓词,最后利用有向图的深度优先搜索对本体图进行遍历,从而实现本体分解。使用该方法进行本体分解,时间复杂度为线性的O(n+e)(n为本体图中顶点数,e为本体图中弧数),远小于传统方法的O(n2)。

基于图遍历的计算DEM数据洪水淹没范围的算法

针对数字高程模型(digital elevation model,DEM)大区域数据量大,而常用的洪水淹没算法(如种子蔓延法)不适用于对DEM的分块计算和分次存储,且用时和耗内存大,设计了一种使用图遍历来有效计算洪水淹没范围的算法,对DEM数据分条带读入计算机内存,然后采用块码压缩方式将潜在淹没区域压缩成块存入磁盘,使用广度优先搜索的图遍历方法读取数据。该算法设计逻辑清晰、实用性强且运算效率高,适用于大范围地形复杂的淹没区域。选取北京市、四川省的DEM数据进行实验,实验结果验证了该算法满足计算快速、占用内存少的要求。

对数空间可构造的无向图遍历序列

研究了为无向连通子图设计环状遍历序列(TSC)的空间复杂性问题。通过定义对数空间的Cook归约,分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系,证明了TSC问题以及无向图遍历问题是对数空间可解的,并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。

图遍历在皮肤老化量化分析中的应用

皮肤老化程度的量化分析对护肤品的研制及其疗效的评估具有重要的工程价值。针对这个问题,研发了一套适用于亚洲人的皮肤老化量化分析系统,该系统的一个核心技术就是对皮沟图像进行量化分析,其中使用图遍历来计算皮沟段长度和皮沟段间角度是量化分析的关键。详细介绍了其实现原理,并给出了具体的Matlab代码。

基于A＊算法和图遍历的烟草物流VRP的研究

同发达国家相比,我国的物流成本明显偏高,因此如何在日益激烈的竞争环境下,降低自己的物流成本,成为了众多企业关注的焦点。以烟草行业物流为基础,积极探索降低物流成本的方法。通过对烟草物流过程中的核心环节烟草配送的研究,在配送最优路径搜索过程中,采用A*算法,并在此基础上结合图的遍历进行物流调度优化,可以快速有效地找到配送的最优路径,从而大大地降低了烟草配送的成本。通过福建中烟项目的实行,也很好地证明了这一点。

图计算体系结构和系统软件关键技术综述

图计算作为分析事物之间关联关系的重要工具,近年来已成为各国政府及公司争夺的关键技术.学术界和工业界在图计算体系结构和系统软件关键技术方面取得了一定进展.然而,现实场景图计算大多具有动态变化、应用需求复杂多样等特征.这给图计算在基础理论、体系架构和系统软件关键技术方面提出了新的需求,同时也带来了新的挑战.为应对这些挑战,科研人员提出了一系列图计算系统或图计算加速器,通过高性能计算、并行计算等技术来优化图计算过程.综述国内外图计算体系结构和系统软件关键技术的研究发展现状,对国内外研究的最新进展进行归纳、比较和分析,并结合国家发展战略和重大应用需求,选取与我国国计民生密切相关的领域,从典型应用分析总结图计算相关技术的行业进展.最后,就未来的技术挑战和研究方向进行展望.

基于图结构的空间同位模式挖掘

空间同位模式反映了不同地理要素分布的依存关系,是地理学第一定律的体现,也符合空间大数据分析重在揭示事物关联特征的目标。空间同位模式挖掘需要顾及空间分布耦合机制,探测空间邻近关系及基于支持度等指标分析高频共生模式。现有方法多在判定邻近关系的同时搜索共生模式,导致在挖掘高阶共生模式时需要实时修正几何邻近关系,在复杂系统下丧失计算过程的灵活性。考虑到图数据蕴含的拓扑连接信息与空间同位模式相契合,本文提出一种基于图结构的空间同位模式挖掘方法。该方法一步完成几何上的邻近关系探测,然后在图数据库中通过子图搜索完成逻辑上的同位模式判别。首先,基于Delaunay三角网构建自适应邻接图,利用自适应邻接过滤器删除无效连接。然后,通过候选子图的不断连接、剪枝、生长,逐步从N元递推获取N+1元候选同位模式。最后,通过计算支持度指标并与预定义阈值比较以确定空间同位模式。本文基于不断生长迭代的图遍历思想提升了空间同位模式挖掘面向更复杂的空间场景的普适性。试验表明本文方法具备高效的挖掘能力,相较传统算法,在多元空间同位模式的挖掘任务中效果更优。

图的深度优先遍历的C语言实现

图的深度优先遍历 ,是对图中的每个顶点进行访问且不能重复访问 ,而我们要遍历图 ,不是在它的逻辑结构上来实现 ,而是要在内存中来实现 ,在这里我们可以先把图采用邻接表方式将图存储起来 ,然后进行深度优先遍历。

基于图遍历的自适应调色板图像密写方案

提出了一种新的基于图遍历的自适应调色板图像密写方案。将调色板中各颜色视为图节点,利用颜色间的亮度差和欧氏距离,构建颜色图。应用图的遍历为颜色节点,分配秘密比特。嵌入秘密信息的过程中,利用相邻像素颜色间的相关性,建立自适应嵌入准则。对比实验结果表明,提出的密写方案具有较大的嵌入容量,并保持很好的图像质量,与其他的密写方案相比,提出的方案更能抵抗直方图特征函数(HCF)统计分析。

基于图论深度遍历算法的智能变电站光纤虚实回路对应方法研究

智能变电站以光缆和软件逻辑替代控制电缆,光纤回路及其承载信息无法直观可视,光纤回路运维困难。目前,国内外在该方面的研究主要集中在逻辑回路的描述方法和建模,光纤物理回路描述方面缺少系统性研究,无法解决光纤回路可视化问题。文章基于图论深度遍历理论,提出了一种智能变电站光纤物理回路与逻辑回路对应方法。该方法将SPCD文件描述的虚回路抽象为邻接矩阵描述的节点连接关系,并通过图论深度遍历算法,确定了智能变电站虚实回路的映射关系,检索出智能变电站虚实回路全路径,解决了光纤回路及其承载信息可视化难题。

图的广度优先遍历的算法实现

图的广度优先遍历与树的按层次遍历相似,遍历的思路是对图中的每个顶点进行访问且只访问一次.要遍历图,首先要把图采用某种存储结构存到内存之中.本文采用邻接表存储,并在此基础上进行广度优先遍历.

图的全遍历方法的研究及实现

本文给出了图的全遍历方法及其适合编程的算法。

图的遍历在烟草物流配送中的应用

我国的烟草行业比较庞大,烟草物流配送路线的选择以及配送的难度比较大,物流配送成本高。本文先分析了烟草行业物流配送的现状,然后介绍了图的遍历算法,最后以烟草公司客户分布情况的虚拟数据来进行模拟,将图的遍历算法思想应用于烟草物流配送系统中,对配送路线进行优化,它有助于提高物流配送系统的效率。

基于DFS图的遍历路径优化分析

深度优先搜索是图的遍历的一种重要方法,在一些网络拓补结构、DNA网络等复杂图形分析中有很广泛的应用。传统的深度优先搜索,从某一节点开始,依次遍历此节点所有相邻且未被访问的节点,其下一跳节点的选择往往不是最优的。文章通过对当前节点所有未被访问的下一跳节点计算其到所有未访问节点路径总和,选择最优的一个节点作为下一跳节点,使得深度优先搜索在图的遍历过程中总的搜索路径大大减少。

P2P随机图的一种遍历改进算法

论文通过对随机有向图(n,k)广度优先遍历算法的改进,提出了一种改进型的拓扑遍历算法,从而加快P2P网络中拓扑生成的速度。同时验证了在拓扑生成中如何通过选择根跳距最大限度地加快遍历的速度,使拓扑图的时间较短,避免造成生成拓扑的图的强连通性。