BHP：面向BSP模型的负载均衡Hash图数据划分

图数据划分是基于BsP（bulksynchronousparallel）编程模型的大规模图处理系统中一个关键技术问题。传统的图划分技术需要多次迭代,时间复杂度过高,且划分结果不具有图顶点到分区的映射信息,因此这些算法并不适用于BSP模型下的数据划分。提出了一种新的面向BSP模型的负载均衡Hash数据划分算法（balancedHashpartition,BHP）。为了实现各个分区的出边数尽可能均衡,该算法引入了虚拟桶的概念,通过贪婪算法将虚拟桶重组为实际分区,保证了每个实际分区负载均衡,同时数据本地化策略使本分片上的数据尽可能地保留在本节点上,从而减小在数据加载时的数据迁移开销。从三个方面对比了BHP算法和经典Hash算法的性能,结果表明BHP算法能够提高作业的执行效率,减少消息发送的数量,有效解决了经典Hash算法的负载不均衡和分区间交互边过多的问题,当数据量变大时,效果尤为明显。     

图数据分析系统计算模型综述

随着大数据时代的到来,图作为一种表示和分析大数据的有效方法,正成为学术界和工业界广泛关注的焦点.图数据具有规模巨大、耦合性强、动态变化等特点,需要新的计算模型支持高效的图计算系统对大规模图数据进行处理.对图计算系统计算模型的研究现状进行了调研和综述,首先介绍图计算系统的产生和发展,然后将主流图计算系统中的计算模型按照计算对象分为:结点中心计算模型、边中心计算模型、路径中心计算模型和子图计算模型四类,重点介绍结点中心模型的应用和性能,最后对图计算模型的发展过程进行总结,并展望图计算模型未来发展方向.     

选择-验证-过滤:一种迭代的子图包含查询处理机制

近年来,图模型广泛应用于生物信息、计算化学、语义网等领域.目前,"过滤-验证"机制被广泛用于子图包含查询,即首先根据图数据的特征构造索引,然后根据索引产生候选集,最后对候选集中的每一个图进行子图同构验证.在这类算法中,"过滤"阶段是关注的重点,力争过滤掉更多的数据;而"验证"阶段则只是单纯地进行候选图子图同构检测,并没有进一步优化查询性能的可能.因此,提出了一种新的子图包含查询的迭代处理机制:"选择-验证-过滤",可利用从子图同构验证过程中得到的信息,结合数据库中图数据之间的相关关系,进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证,然后根据本次验证得到的信息,结合图数据之间的子图映射关系,进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果,而若验证不成功,则可以缩小下次迭代的查询搜索空间.为提高验证成功概率,提出了一种基于搜索空间预测的图选择策略.大量实验表明,该算法具有较"过滤-验证"机制更高的查询处理性能.     

分布式多维大图迭代计算性能优化方法

大规模图的复杂挖掘算法通常需要高频迭代分析，而在计算与存储方面扩展性良好的分布式计算是提高处理效率的有效方案.然而，图顶点之间存在自由分布的边关系，会在分布式计算任务之间产生大量消息，由此在迭代过程中产生的巨大通信开销严重制约性能收益.已有工作在传统消息推送框架下采用合并和备份等技术降低通信代价，但主要面向结构简单、易优化的单维消息类算法，并不适用于结构复杂的多维消息类算法，也难以与当前最先进的消息按需拉取框架兼容.因此提出一种新型轻量级顶点备份机制，通过备份顶点的按需同步以及本地消息的按需生成，可完美继承拉取框架在容错和内存管控等方面的系统优势，同时显著降低通信代价.此外，通过考虑通信收益与负载偏斜代价，可计算最优阈值以提高整体性能.最后在大量真实数据集上验证了相关技术的有效性.     

面向大规模二部图的分布式Tip分解算法

Tip分解作为图数据管理领域的热点研究问题,已被广泛应用于文档聚类和垃圾邮件组检测等实际场景中.随着图数据规模的爆炸式增长,单机内存已无法满足其存储需求,亟需研究分布式环境下Tip分解技术.现有分布式图计算系统的通信模式无法适用于二部图,为此,首先提出一种基于中继的通信模式,以实现分布式环境下处理二部图时消息的有效传递...     

基于图神经网络的多维度池化图分类

目前很多处理图数据的图神经网络方法被提出,然而大多数研究侧重于对特征聚合的卷积层的研究而不是进行下采样的池化层.此外,形成聚类簇的池化方式需要额外计算分配矩阵;节点得分的池化方式排名方式单一.为解决上述问题,提高图分类任务的准确性,本文提出了一种新的基于多维度信息的图池化算子MDPool.该模型使用节点特征信息以及图拓扑结构信息,获取不同维度下的节点得分.使用注意力机制归纳不同维度下的得分权重,生成更为健壮的节点排名,基于节点排名自适应选择节点集合生成诱导子图.提出的MDPool可以集成到多种的图神经网络结构,将MDPool池化算子与图神经网络卷积层堆叠形成编码解码模型EDMDPool.在4个公开数据集的图分类任务中, EDMDPool均高于现有基线模型.     

图嵌入算法的分布式优化与实现

随着人工智能时代的到来,图嵌入技术被越来越多的用来挖掘图中的信息.然而,现实生活中的图通常很大,因此分布式图嵌入技术得到了广泛的关注,分布式图嵌入算法面临着两大难点：（1）图嵌入算法多种多样,没有一个通用的框架能够描述大部分的算法;（2）现在的分布式图嵌入算法扩展性不足,当处理大图时性能较低,针对以上两个挑战,本文首先提出一个通用的分布式图嵌入框架,具体地,本文将图嵌入算法中的采样流程和训练流程进行解耦,使得框架能够较好的表达多种不同的算法;其次,本文提出了一种基于参数服务器的模型切分嵌入策略,具体地,本文将模型分别切分到计算节点和参数服务器上,同时使用数据洗牌的操作保证计算节点之间没有模型交互,从而大大减少了分布式计算中的通信开销,笔者基于参数服务器实现了一个原型系统,并且用充分的实验证明了在不损失精度的前提下,基于模型切分的策略能够比基线系统取得更好的性能.     

基于互补子词单元词图融合的集外词识别*

混合模型在进行集外词识别时,采用不同类型的子词单元通常具有性能上的互补性.基于此种情况,文中提出互补子词单元词图融合的集外词识别方法.首先分别采用音节和字母音素对搭建2套具有性能差异性的混合模型系统.然后获得这2套系统的识别词图,并合并处理词图中的子词单元.最后分别采用基于词图并集和基于词图交集的融合策略融合处理后的词图,得到更好的集外词识别结果.实验表明文中方法性能优于单系统及ROVER方法.     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

基于强化联邦图神经网络的个性化公共安全突发事件检测方法

近年来,将公共安全数据转换为图的形式,通过图神经网络构造节点表示应用于下游任务的方法,充分利用了公共安全数据的实体与关联信息,取得了较好的效果.为了提高模型的有效性,需要大量的高质量数据,但是高质量的数据通常归属于政府、公司和组织,很难通过数据集中的方式使模型学习到有效的事件检测模型.由于各数据拥有方的关注主题与收集时间不同,数据之间存在Non-IID的问题.传统的假设一个全局模型可以适合所有客户端的方法难以解决此类问题.本文提出了基于强化联邦图神经网络的公共安全突发事件检测方法PPSED,各客户端采用多方协作的方式训练个性化的模型来解决本地的突发事件检测任务.设计联邦公共安全突发事件检测模型的本地训练与梯度量化模块,采用基于图采样的minibatch机制的GraphSage构造公共安全突发事件检测本地模型,以减小数据Non-IID的影响,采用梯度量化方法减小梯度通信的消耗.设计基于随机图嵌入的客户端状态感知模块,在保护隐私的同时更好地保留客户端模型有价值的梯度信息.设计强化联邦图神经网络的个性化梯度聚合与量化策略,采用DDPG拟合个性化联邦学习梯度聚合加权策略,并根据权重决定是否对梯度进行量化,对模型的性能与通信压力进行平衡.通过在微博平台收集的公共安全数据集和三个公开的图数据集进行了大量的实验,实验结果表明了提出的方法的有效性.     

基于空间近邻查询的移动医疗呼叫算法

随着大数据时代的到来，传统的计算机因为单机资源有限、运行速度慢、分布式处理支持差，已满足不了现行的医疗体系中的大数据处理需求，基于时空数据的移动医疗呼叫系统方法可以很好地解决这些问题。在移动云计算环境下研究[k]最近邻查询算法是当前一个热点问题，支持可扩展和分布式的空间数据索引对于kNN查询的效率影响很大，目前已有的查询算法不适合并行化或者会导致内容冗余。将MapReduce分布式处理技术与空间kNN查询方法相结合，设计可以快速检索到满足用户查询需求的医生位置信息的移动医疗呼叫算法。提出并构建了一个新的分布式空间数据索引方法：倒排Voronoi图索引，它将倒排索引和Voronoi图索引进行结合；提出了一种基于MapReduce的利用Voronoi图来处理kNN查询的高效算法，其在分布式环境下可以有效提高查询效率；用真实的和仿真的数据集来进行大量实验评估，实验结果表明所提出的方法具有良好的高效性和可扩展性。     

RIAIL:大规模图上的可达性查询索引方法

图被广泛用来建模在社交网络、语义网、计算生物学和软件分析中的应用.可达性查询是图数据上的一种基础查询.当前,针对图上的可达性查询已经提出了一些索引算法,但是它们不能灵活地扩展到大的图数据.因此,提出了一种索引方法RIAIL(reachability index augmented by interval labeling).RIAIL将结点的标记信息表示成四元组.前两个元素是区间标记,编码生成树的可达性信息,后两个元素编码非树边的可达性信息.RIAIL查询时只需索引且索引创建代价小.最后,通过大量真实和人工生成数据集上的实验说明,RIAIL能够高效地处理可达性查询,并且可以简单地扩展到大的图数据.     

信息化运维系统的图模型存储

基于新型IT基础设施,如云计算环境,大数据平台等,信息化应用获得了灵活可靠的底层服务.同时通过新型服务形式,如物联网应用,移动端服务等,增强了业务服务能力.但这些新技术使得信息运维面临运维对象频繁变化,对象关系不断调整,运维数据格式多样的难题.本文基于电网企业当前运维现状,给出一种基于图模型的运维数据存储设计,提高了对动态,非结构化运维数据的处理能力.经实测验证,模型处理普适性更广,数据读写性能稳定,方案有效解决了新运维形式下的电网企业信息化运维系统的业务难点.     

多步前进同步并行模型

提出一种并行计算模型——多步前进同步并行（delta-stepping synchronous parallel,简称DSP）模型和一种形式化表示方法.针对大同步并行（bulk synchronous parallel,简称BSP）模型同步次数多、收敛速度慢的特点,该模型能够有效地减少同步次数和通信开销,进而加速算法的收敛.通过形式化表示和迭代过程推导,发现DSP是一种比BSP更一般的并行计算模型.在BSP的基础上,DSP将BSP中执行1次的局部计算变为执行多次.理论分析和验证实验表明,新增加的局部计算步可以进一步挖掘和利用隐藏在数据分区中的局部性.同时,通过“计算换通信”原理增加的局部计算并非越多越好.最后的实验结果显示,DSP模型能够有效地效减少算法的迭代轮数及收敛时间,对BSP的加速可高达到数倍乃至数十倍.     

并行计算模型在异构计算环境中的研究

近年来异构并行计算在高性能科学计算和通用应用领域受到广泛研究。本文结合多种代表性并行计算模型，给出异构环境中的HBSP模型和程序开销计算方法。采用基于消息长度的线性模型使通信开销的计算更精确，解除原有BSP模型对h-rela-tion的限制，使程序和算法在异构环境中的设计更加灵活。当构成BSP计算机的各处理机速度相同且原有BSP算法达到最优（即各处理机上所分配的计算量与通信量完全均衡）时，HBSP模型等同于原有模型。     

基于增量信息索引的子图查询算法

当前图数据库中的子图同构查询算法主要是依赖倒排索引,然而处理那些具有庞大数据的数据库和复杂的查询愈发成为挑战。研究目的是设计一个算法,使用新的索引作为查询处理的核心,记录查询图的每一个细小改变,并使用一种特殊的数据结构来维护。先是引出一个索引算法,然后逐渐分析整个索引、查询过程,并利用该算法实现一个系统,最后在不同数据集和查询上进行实验。实验证明了该算法具有良好的时间、空间效率和扩展性。新的索引算法能够支持更大的查询图和更加灵活的查询。通过实现的系统和其他系统的对比实验,验证了算法的有效性。     

基于可视界面的社交媒体搜索系统

针对社交媒体数据搜索中存在的消息文本短、不利于构建索引,排名列表形式单一、无法展现社交媒体数据的整体结构的问题,通过挖掘社交媒体数据隐含的多重语义特征,强化索引结构,提出基于可视分析方法的搜索系统,采用交互式界面可视化表达语义特征,使得搜索更准确.以推特数据为研究对象,基于时间上的语义相关性,首先抽取数据中隐含的话题和命名实体集合;在此基础上构建层次语义图模型,简化数据的内在语义关系,同时为可视化搜索提供必要的索引结构;用户浏览数据时,分裂环形图表示数据的多重语义特征,系统提供多种交互方式方便用户探索更多信息.案例分析结果表明,相对于连线和气泡图特征模式,分裂环形图更加明显,方便用户寻找关注的消息;用户调查结果反映出该方法较传统的搜索方式更容易找到想要的结果.     

基于图结构索引的分布式OLAP加速方法

随着业务数据的规模增大,一些重要的应用场景需要使用分布式在线分析处理(OLAP)支持大规模数据的分析,例如商务智能(BI),企业资源计划(ERP),用户行为分析等.同时,分布式OLAP打破单机存储的限制,可以将数据放在内存中以提升OLAP的处理性能.然而,基于内存的分布式OLAP在消除磁盘I/O后,性能瓶颈转移到了连接操作.连接操作是OLAP中的一种常用操作,会进行大量的数据读取与计算操作.通过对现有的几种连接操作方式进行分析,提出了一种能够加速连接操作的图结构索引以及基于图结构索引的连接操作方式LinkJoin.图结构索引通过用户所指定的连接关系,将数据在内存中的位置以图结构的形式进行存储.基于图结构索引的连接方式,不仅能够有等同于哈希连接的较低复杂度,而且在执行过程中能减少数据读取与计算操作次数.将目前先进的开源内存OLAP系统MonetDB从单机系统扩展成分布式系统,并且在该系统上设计与实现了基于图结构索引的连接操作方式.针对该系统的图索引结构,列式存储以及分布式执行引擎这3个重要方面,进行一系列设计与优化,以提升系统的分布式OLAP处理性能.测试结果表明,在TPC-H标准测试中...     

基于拓扑序列的DAG子图包含查询算法研究

图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,...     

NVSA:一种具有可变节点值的查询图搜索算法

图模型作为一种重要的数据结构,常被应用于众多不同领域并被广泛研究。随着图数据规模的日益增大,大图上的子图搜索问题变得极为重要。然而,目前已有的研究成果在大图上的执行效率并不太理想,而且没有考虑查询图上存在节点值可变的情况。为解决具有可变节点值的查询图在大图上的搜索问题,本文提出基于双索引的NVSA算法。首先通过合并相邻同类点构建CP索引和Vin索引,然后根据索引结构优化加速子图搜索算法。真实数据集上的实验表明,NVSA算法具有有效性和高效性。