面向大图子图匹配的多GPU编程模型

子图匹配是复杂网络中进行数据挖掘的重要手段。近年来,基于图形处理器(GPU)的子图匹配算法已展现明显的速度优势。然而,由于大图数据的规模宏大以及子图匹配的大量中间结果,单块GPU的内存容量很快成为了处理大图子图匹配算法的主要瓶颈。因此,提出了一种面向大图子图匹配的多GPU编程模型。首先,提出了基于多GPU的子图匹配算法框架,实现了子图匹配算法在多GPU上的协同操作,解决了GPU大图子图匹配的图规模问题。其次,采用了一种基于查询图的动态调节技术来处理跨分区子图集,解决了图划分导致的跨分区子图匹配难题。最后,结合GPU单指令多线程(SIMT)架构特性,提出一种优先级调度策略保证GPU的内部负载均衡,并设计了共享内存的流水线机制优化多核并发的缓存争用。实验表明,多GPU编程模型能够在数十亿级别的数据集上得到正确的匹配结果,与最新的基于GPU的解决方案相比,该算法框架能够获得1.2~2.6倍的加速比。

一种改进的基于BSP的大图计算模型

伴随大数据的涌现,云存储和计算技术近年得到长足发展.图数据是一种重要而普遍的大数据,在生物信息学、社会网络、化学信息学等领域都有众多应用.因此,大图计算作为大数据分析应用的典型代表,正成为云端负载的重要组成部分.目前,高可扩展性的图计算主要依赖于高性能计算解决方案,需要进行环状(或网状)计算机网络之上的高效全集合通信.然而,在通用计算集群和云计算基础设施上实现基于环状计算机网络的算法时,低效的网络通信将导致巨大的系统延迟.因此,这就要求那些基于云端的大数据计算平台和系统具备十分良好的水平可扩展性.但是,大图的幂律分布和缺乏局部性使得设计一套高度可扩展的大图计算系统变得更具挑战.为此,文中提出了一种面向通用计算集群的可扩展大图计算模型.专注于水平扩展能力,设计了一种新颖的基于分离器-合并器BSP的图计算方法,能够提供原生的负载平衡,仅需很低的通信开销.从而,图数据规模的增大可以通过增加计算节点数量得以解决.最后,在一个图数据通用测试集上,通过大量实验验证了所提模型和方法的有效性和高效性;结果显示,相比经典的以顶点为中心的BSP大图计算模型和其他主流大图计算系统,所提改进的基于BSP的大图计算模型能够提供更好的水平可扩展性.

OnFlyP:基于定向边交换的分布式在线大图划分算法

随着大数据时代的到来,基于云环境的大图迭代计算已经成为新的研究热点,其中提高图划分算法的执行效率和降低划分后子图之间的通信边规模是改善计算性能的关键.已有工作主要分为离线划分和在线划分两大类,无法在执行效率和通信边规模方面同时满足迭代处理需求.文中针对真实世界的大图,提出了聚簇系数概念,定量分析了顶点分布的局部性,以此为基础设计了一种基于定向边交换模型的分布式在线图划分算法(OnFlyP),可在迭代计算的数据加载阶段快速完成图划分,同时通过出边的交换有效降低通信边规模,以满足迭代计算需求.OnFlyP采用实时控制和最小对称矩阵控制实现负载均衡,前者具有较高的执行效率,而后者对降低通信边规模有较好的优化效果,可根据实际应用的处理需求灵活选择.最后,作者使用多种真实数据验证了OnFlyP算法的有效性.

大图数据上顶点驱动的并行最小生成树算法

最小生成树(minimum spanning tree,MST)是图论中最为经典算法之一.基于MST结构的聚类、分类和最短路径查询等复杂图算法,在效率和结果质量方面均有显著提高.然而,随着互联网的迅猛发展,图数据规模也变得越来越大,包含千万甚至上亿个顶点的大图数据越发常见.因此,如何在大图数据上实现查询处理和数据挖掘算法已成为亟待解决的问题之一.除此之外,由于大图数据的动态性特征,如何动态地维护算法结果也势必成为最受关注的问题之一.针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题,首先提出了分区Prim(partition Prim,PP)算法,基于此提出了顶点驱动的并行MST算法——PB(PP Boru。vka)算法,并论证了PB算法的正确性.另外,基于MapReduce和BSP框架实现了PB算法.针对只删除动态图特征,提出了MST维护算法,以实现高效的增量计算.对提出的计算和维护算法进行了代价分析和比较.最后,使用真实和模拟数据集,验证了PB算法和维护算法的有效性、高效性和可扩展性.

基于结构分解的动态图增量匹配算法

在大数据时代,图数据的规模急剧增长,增量图模式匹配技术能够在数据图发生变化时避免重新对整个数据图进行匹配,进而减少匹配时间,提高整体执行效率,因此成为研究热点。然而,现有的增量匹配算法处理规模较大的模式图时效率会降低。针对该问题,提出了一种基于结构分解的增量图模式匹配算法Inc_CFLS。在匹配过程中,为中间匹配结果构建高效索引,用于后续的模式匹配计算。基于构建的索引信息对数据图增加边事件进行分类,进而为每类增加边事件设计查询剪枝优化策略,从而有效提高匹配效率。在真实数据集上进行实验,结果表明Inc_CFLS算法比目前最好的增量匹配算法在执行效率上平均提升了1~2倍,能更有效支持大规模动态图上的模式匹配。

知识关联视角下的文化遗产知识大图研究:理论、方法和趋势

[目的/意义]文化遗产知识大图研究是人文与技术交叉融合的新研究领域,借助智能化的理论和方法对文化遗产资源进行关联和融合,是文化遗产“活起来”的关键,对于中华优秀传统文化的传承发展具有重要意义。[研究设计/方法]从知识关联视角,应用文献分析法、专家调研法等,系统梳理当前文化遗产知识大图研究的理论和方法,并构建了文化遗产知识大图的理论框架与方法体系,探析了未来研究趋势。[结论/发现]推进文化遗产知识大图的研究,应以知识关联为基础,以文化基因为核心,加强跨学科的理论融合创新,进一步与脑机融合、元宇宙等新技术结合,构建知识驱动的方法体系。[创新/价值]提出知识关联视角下的文化遗产知识大图研究理论框架、方法体系和研究趋势。

金融股权知识大图的知识关联发现与风险分析

金融机构的复杂股权网络是系统性金融风险的微观成因和传导渠道.因此,发现和分析股权网络中的关键风险特征结构对金融监管有着重要意义.本文从知识关联理论出发,基于大规模股权网络构建金融股权知识大图,在此基础上提出了多层股权穿透(MEP)算法,揭示以金融机构为中心的穿透式多层股权网络;提出了关键股权路径发现(CEP)算法,发现金融机构之间的关键股权路径.本文结合案例对以上基于知识关联的股权风险结构进行了实证分析,并对MEP和CEP算法进行了性能分析与对比.基于真实数据的实证分析和性能分析表明,与传统的股权结构分析方法相比,本文所提出大数据算法能够更加高效和准确地发现和分析关键股权风险结构,支撑系统金融性风险的穿透式监管.

给定权集的赋权双圈图的谱半径(英文)

令BWn,n,n＋1表示阶为n的赋权双圈图的集合，W = {w1,w2,...,wn＋1}，其中w1 ≥ w2 ≥... ≥ wn＋1 〉 0为权集合．本文确定了它们中谱半径最大的赋权双圈图的结构及部分权值的分布情况．

临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——指数不小于h+3的情形

本文通过临界h棱连通图的指数概念,讨论了指数不小于h+3的p阶临界h(≥4)棱连通图的最大棱数问题。

“大图学”学科的构筑与建设——图学类课程体系的融贯研究

"大图学"概念的提出及其学科体系的构筑充分适应了社会经济建设及学科发展的需要。图学类课程体系的融汇与贯通是图学学科发展方向的内在要求。本文在查阅丰富资料,组织多次调研的基础上,借鉴了目前日本和美国工程制图学科的课程设置情况,从教学目的、教学体系、教学内容和教学模式四方面着重研究分析了图学类诸门具体课程之间的内在联系机理及先进技术手段在其中的应用。

工程建模中的图学美学

图学和美学作为工程建模的重要组成部分,不仅是模型建立的基础,也是提升学生审美能力的关键。审美情趣的提高,使学生感受到图形美的存在,图形美的力量会促进学生对工程图形建模完美程度的要求,提高图形设计和建模能力。以工程建模中图学和美学的一般概念为切入点,分别从工程制图中的图形美学、工程建模中的图学美学以及融合大图学与智能计算的智能建模图学美学等方面,阐述了工程制图和工程建模中图学和美学的表现形式,展望了智能建模的发展前景。基于图学美学的工程建模课程教学,提出基本要求和教学实施方式。结合图学和美学,对新时代工程图学和建模的教育教学进行了思考。

知识图谱数据管理系统的设计与实现

本文在调研考察了多种图数据库的基础上,综合考量了分布式、扩展性、可用性、查询语言、容错性、存储后端、一致性等因素,并充分结合知识图谱数据自身所具有的特点,选取了当前流行的图数据库系统Titan作为底层存储,并对其进行进一步深入的研究,在此基础上实现了一个知识图谱数据管理系统。此系统能对知识图谱数据进行管理,包括数据的导入、数据的查询以及数据的修改,能支持billion数据量的存储,以及图上的基本操作,这些操作响应时间都在秒级。

大图结构特征对划分效果的影响

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性。然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6 233和316。实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。

知识图谱数据管理系统设计

文章在考察了大量图数据库的基础上,综合了分布式、扩展性、可用性、查询语言、容错性、存储后端、一致性等因素,并充分结合知识图谱数据自身所具有的特点,选取了当前流行的图数据库系统Titan作为底层存储,并对其进行进一步深入的研究,在此基础上实现了一个知识图谱数据管理系统。此系统能对知识图谱数据进行管理,包括数据的导入、数据的查询以及数据的修改,能支持billion数据量的存储,以及图上的基本操作,这些操作响应时间都在秒级。

理想化的互极大图

设R是有1的交换环,M是R-模,R(+)M是环R对于R-模M的理想化.讨论了理想化R(+)M的理想、极大理想和可逆元与环R的理想、极大理想和可逆元之间的联系,并利用理想化的代数性质,讨论了R(+)M的互极大图的子图Γ2(R(+)M)-J(R(+)M)的直径和围长.

门槛图与度极大图(英文)

证明了门槛图与度极大图是一类图的两种不同说法，同时用图的对角限制极左矩阵刻画这一类图的结构．

给定顶点数和边数的连通图的Q-谱半径的界(英文)

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和,其特征值记为q_1≥q_2≥…≥q_n.设C(n,m)是由n个顶点m条边的连通图构成的集合,这里1≤n-1≤m≤((n/2)).如果对于任意的G∈C(n,m)都有q_1(G~*)≥q_1(G)成立,图G~*∈C(n,m)叫做最大图.这篇文章证明了对任意给定的正整数a=m-n+1,如果n>-1/2+a+1/2(1+12a+12a^2)^(1/2),那么n<q_1(G~*)<n+1,进而得到,对任意的G∈C(n,m),只要n>-1/2+a+1/2(1+12a+12a^2)^(1/2),就有q_1(G)<n+1.

一种基于数据图划分的关系数据库关键词检索方法

不同于常用的一次性将图加载入内存的检索方法,提出了一种基于数据图划分的关系数据库关键词检索方法,该方法首先将大图细分成多个相互之间具有简单连通性的小图并存储于缓存中,然后通过超图查询算法获取与查询条件相关的子图,进行关键词检索获取候选结果时,只需加载相关子图并恢复子图的初始结构,通过遍历子图获得最终结果.实验表明,该方法可以有效解决对无法放入内存的大型数据图的处理问题,使得关系数据库关键词检索实用于庞大而复杂的数据图中而不受内存约束.

判定大型图中可到达性的随机区间标记索引

提出一种基于随机区间标记理论的可到达判定的方法 RIABG,它可以有效地处理非常大型的图,并且具有良好的可扩展性。RIABG具有线性的检索时间和空间复杂度,查询时间可以是常数时间,也可以根据图的大小而进行线性变化。真实数据集上的实验表明,RIABG可以有效处理大规模有向图的可达性判定问题。

大规模图数据划分算法综述

对大规模图数据划分算法进行了总结,介绍了并行环境下图计算模型,详述了大规模静态图划分算法和动态图划分算法,归纳了这些算法的优缺点以及适应性。最后,指出了关于大图划分尚未探索的有意义的研究课题。