Dominance-Partitioned子图匹配在大RDF图

文摘

子图匹配大图已经成为图像分析领域的一个热门研究课题,具有广泛的应用程序包括问答和社区检测。然而,传统的切边策略破坏不可分割的结构知识在一个大的RDF图。在负载均衡的前提下在子图分割,dominance-partitioned策略提出了将一个大RDF图知识结构的前提下。首先,dominance-connected模式图提取模式图构建dominance-partitioned模式超图,划分图模式为多个都子图模式。其次,dominance-driven谱聚类策略是用来收集子图模式到多个集群。第三,dominance-partitioned子图匹配算法设计进行所有cluster-partitioned RDF图的同构子图。最后,实验验证评估复杂查询的策略具有更高的效率,它有一个更好的可伸缩性在多个机器上和不同的数据尺度。

1。介绍

子图匹配问题是一个根本的问题在图搜索,这是一个np完全问题[1]。具体地说,给定一个查询图问和一个大数据图 ,子图匹配问题是提取所有同构的子图问在 。然而,一个方面是查询图的复杂结构降低了查询精度和性能在大数据图,喷发规模的数据增长的现实世界。另一个方面是,社交网络的数据往往是组织作为一个rich-semantical结构。在本文中,我们将研究大型rich-semantical RDF图的子图匹配问题。

尽管知识结构的复杂性和多项式时间的子图匹配问题,最近的现有的研究取得了很大的进步在改善子图匹配的性能在大知识图在分布式环境中。

一个方面是将RDF数据封装到triple-based关系表(2,3),确保triple-based不可分割的知识的完整性。因为关系方法忽略RDF数据的内在结构图表,一个昂贵的开销消费过度关系表的连接操作。另一个方面是管理RDF数据到本地图格式,通常采用邻接表索引RDF数据(4- - - - - -6]。以来的最低切边策略在大图表抑制不可分割的结构知识,巨大的中间结果严格平衡加载分区RDF子图。

确保完整性的不可分割的知识基于格式,大多数研究人员致力于模式图形分解成异形子图。StarMR [7,8)分解查询图一组星形的子图,然后,两个优化技术被用来过滤无效的输入数据,减少数据的恒星。CFLMatch [9)推迟了聚合操作在一个树状索引由core-forest-leaf查询分区模型。

1.1。贡献

在本文中,我们致力于有鱼形图案图分解为子图,考虑到由于和RDF图的拓扑结构。然后,有子图是集群和用于指导大型RDF的分区图。最后,子图匹配算法设计进行所有分区的RDF子图同构子图。我们的贡献说明如下:我们提出了一个占主导地位的模式连接图来提取模式的支配关系图,包括节点和节点内涵外延的关系的关系。节点外延和内涵的关系模式中发现的主导和semidominant节点图。然后,都有模式子图通过主导node-centered扩张。我们设计一个dominance-partitioned模式超图模型都有子图模式。每个hypernode指都有子图模式,每个hyperedge表示之间都有共同的子图子图模式。我们采用dominance-driven谱聚类策略收集都有子图到多个集群模式。dominance-partitioned加权矩阵是第一个由dominance-partitioned超图模式。然后,谱聚类策略是用来收集hypernodes到多个集群基于加权矩阵。我们设计一个状态转换模型来描述的过渡状态改变的候选人,由三个州和六个转变规则。基于状态转换模型,我们分析的影响改变了候选人相邻地区和设计我们的增量维护的策略。我们提出一个dominance-partitioned子图匹配算法进行所有cluster-partitioned RDF图的同构子图。

本文的其余部分组织如下:部分2介绍了预赛对问题的定义和相关的工作。一个框架中提供了一个dominance-partitioned RDF图第三节图,包括dominant-connected模式,dominance-partitioned模式超图和dominance-driven谱聚类策略。第四节提出了一种dominance-partitioned子图匹配算法。实验结果发表在第五节。给出一个结论第六节。

2。预赛

在本节中,RDF图的定义和子图匹配首先得到的是。然后,介绍了相关的研究。

2.1。问题的定义

资源描述框架(RDF) [10)是一个标准的语义模型由W3C组织设计\{脚注https://www.w3.org/community/kg-construct/},它是由一组三元组表示 。每一个三 包括三个部分:一个主题、一个谓词,一个对象。此外,一个三 是成立的我×我×伊尔,在那里我表示一个IRI(国际化资源标识符)l代表一个文字。

定义1 (RDF图)。RDF图是一个有向标记图,形成 。在这里,是一组顶点,E⊆×表示一组定向边缘,l表示一组关于顶点和边的标签,和∪E⟶l显示一个标签函数,指定顶点和边实例化标签。
一个RDF图的标签被列为instance-label, relation-label, attribute-label,根据资源类型标签和interresource RDF数据的关系。RDF三元组 被认为是,o被命名为类型标签当且仅当两者年代和o虹膜,p是一个类型的谓词,如rdf:类型,rdf:的子类。的年代和o被称为是instance-label,p被命名为relation-label当且仅当两者年代和o虹膜和p不是一个类型的谓词,然后呢p被称为是attribute-label当且仅当o是一个文字。
考虑到RDF图在图1,每个顶点都用一个instance-label或类型标签或标记attribute-label或者文字,每条边被relation-label标记。instance-labeled顶点的集合是收集{Person_A,Person_B,Publication_A,Course_B,Course_C,Department_A,University_A}。type-labeled顶点的集合了,{出版,GraduateCourse,课程,FullProfessor,ResearchAssistant,部门,大学}。literal-labeled顶点的集合被描述为{123 @163.com}。所有边的标签都映射到relation-labels。

定义2(图)模式。一个模式是一个有向图标记图,形成 ,在哪里是一组顶点,ℰ⊆吗×表示一组定向边缘,表示一组关于顶点和边的标签,和ψ:∪ℰ⟶var显示一个标签函数,指定顶点和边的概念标签。
考虑图在图模式2,每个顶点映射类型标签或attribute-label和每条边被relation-label映射。RDF和模式的差异图是图不包含instance-labels模式。此外,图形模式是一个概念网络和每个查询图是图的子图模式。

2.1.1。子图匹配

子图匹配问题是搜索所有可能的数据图的子图图同构的查询问。子图匹配正式定义为子图同构问题,描述的定义3。

定义3(子图同构)。给定一个数据图 和查询图问( ,ℰ′,ℒ′ψ′),问是子图同构,当且仅当存在一个双射的映射米从来这样∀u∈ ,∃米(u)∈ :ℒ′(u]⊆l(米(u)]和∀u,u′∈ ,∃(u,u′)∈ℰ′:(M (u),M (u′))∈E和ℒ′(u,u′)=l((M (u),M (u′))]。
一个查询图问是子图同构数据图吗如果存在一个子图同构映射(子图映射)问在 。简单,考虑图数据和查询数据2和3分别问是子图同构,由于存在子图同构映射米₁{<Person_A,FullProfessor>、<Person_B, ResearchAssistant>、<Course_B,GraduateCourse>}。
的k分区问题RDF图所示定义4。

定义4 (K分区问题RDF图(RG-KP))。给定一个RDF图 ,的KRDF图是指划分分区问题问成k子图,满足 ,这种重叠的成本 子图和最小成本满足条件 。
RG-KP问题在这篇文章中,我们的研究着重于dominance-partitioned策略划分图的拓扑和树状结构模式。然后,dominance-driven谱聚类是用来收集dominance-partitioned模式子图到多个集群。最后,dominance-partitioned子图匹配算法设计进行所有cluster-partitioned RDF图的同构子图。
在本文中,我们专注于直接标记图。这两个问和直接标记图,直接的或间接的边缘不能影响的执行调度子图匹配。因此,占主导地位的连通子图模式和dominance-partitioned模式超图没有graph-labels被定义为一个无向图。表中描述的详细的符号和意义1。

2.2。相关的工作

在本节中,我们主要回顾相关工作triple-based关系和在分布式环境中基于遍历策略。

2.2.1。Triple-Based关系策略

大部分RDF系统存储和索引RDF数据作为一组三表在关系数据库中。SW-store [11]垂直分区为多个RDF三元组属性表。RDF-3X [2,12]和hexastore [3)实现基于索引的查询计划通过直接存储多个安排的三重冗余地 - - - - - -树。彭et al。13)设计了一个RDF图的存储方案来优化图划分和平衡加载查询,在查询处理分为两个阶段:扫描和加入。在扫描阶段,SPARQL查询的查询引擎分解为一组三模式。在加入阶段,首先扫描中间结果绑定到一个左连接树,然后,查询结果是通过左连接树。

分布式系统H-RDF-3X [14和碎片15]水平RDF数据划分为多个计算节点和使用Hadoop作为cross-node查询的通信层。H-RDF-3X RDF图分为指定数量的分区数据子图通过最小边缘切法美逖斯(16]。然后,1-hop或2-hop复制的策略是用来扩展分区的边界数据的子图,确保稳产查询单分区数据子图内可以获得完整的答案。使用两个系统的查询处理RDF三元组的reduce-side策略是扫描在映射阶段和中间结果的最终结果在减少迭代阶段。然而,RDF三元组的迭代映射和减少操作可以进行昂贵的时间消耗复杂拓扑结构的查询图。

减少拓扑查询图的复杂性,查询分解模型,称为TwinTwig [17),设计一个高效的分布式无向图子图枚举算法。S2RDF [18对spark-distributed] SPARQL查询转换成抽样操作计算框架。即使离线建立索引加快网络子图匹配处理,需要支付昂贵的时间消耗指数建设与大规模数据图。三合会(4)结合join-ahead修剪通过RDF图的形式总结locality-based水平分区的RDF三元组成网状分布式索引结构。

2.2.2。基于遍历策略

是基于遍历策略了RDF数据存储在本地图格式,重点建设数据索引和修剪多余的中间结果的规则。

大型数据图的构造指数被用来缩小候选中间结果的搜索空间。BitMat [19)提出了一种压缩位矩阵结构来存储巨大的RDF图,和一个variable-binding-matching算法直接用于生成最终的结果没有索引的中间结果。TripleBit [20.)提出了一个快速和紧凑的系统来存储和访问RDF数据,设计两个辅助索引结构以减少索引选择在查询的成本评估。一个签名技术提出了gStore [21],RDF数据存储在基于磁盘的邻接列表和RDF图变成了签名图像的数据编码和每个实体类顶点。然后, - - - - - -树在数据签名图提出了与光维护开销。加强gStore,重新设计gStore [22]给出了一个新的查询计划生成模块生成查询计划根据不同查询图的结构。此外,它重新设计了顶点编码策略来实现更多的修剪能力和一种新的multijoint算法加快子图匹配的过程。

修剪规则的研究被用来减少冗余处理的中间结果子图匹配,比如三一。RDF (23和悟空5]。三一。RDF是一个分布式的基于内存的图形引擎网络级RDF数据。而不是管理RDF数据在三重商店或位图矩阵,引擎RDF数据存储在本地图格式支持基于RDF图的操作,例如,随机漫步,可达性和社区发现。然而,三位一体。RDF只用单修剪规则以避免冗余的基于路径的中间结果,和一个主机需要聚合所有积极的中间结果。研究[4,5)发现,单机聚合操作可以很容易地进行大查询图的瓶颈,因为巨大的中间结果可能导致内存溢出在单个主机器上。此外,实验(5)表明,聚合操作消耗超过90%的总匹配时间。在实验验证的基础上,悟空采用完整的历史修剪策略来减少冗余的中间结果。然而,聚合操作的成本模型旨在引导一个匹配的顺序在关系数据库中。full-join笛卡尔产品的昂贵的时间消耗应该限制进行了最终结果的效率,但它只使用成本模型基于关系型谓词连接方法指导查询执行。

大多数现有的研究都致力于确保不可分割的知识的完整性。徐et al。24)研究问题的多目标空间关键字查询和语义设计LIR-tree指数整合所有对象的空间和语义信息平衡的方式。王等人。25)创建了一个新的和更完整的知识,提出了一个社交网络k-Dcore框架来检索有效的社区的社交网络。陈等人。26)提出了一个pivot-based分层索引结构 - - - - - -树以无缝的方式集成空间和语义信息,精心设计一个机制来将高维空间语义向量修剪一个低维空间,这样更有效的效果。程等。27]研究自动修复图和一些修补规则,设计了一种分解并加入策略解决寻找图的同构子图的多项式时间复杂性graph-repairing数据规则。分配(28)是一个efficient-distributed策略解决问题的可达性查询大不确定图发现所有的最大一个原始图的子图的步骤减少分布式图形,将问题转换为一个关系加入分布式整合的步骤过程。深NBCN [29日)发现了均匀和multibranch架构模型复杂的氨基酸序列和蛋白质二级结构内部关系序列。

在本文中,我们把模式图形分解成部分减少聚合操作的时间消耗的子图。我们的研究动机是由前面的研究发现一个特殊的结构模式的图。第一个现有研究StarMR [7),分解查询图一组过滤冗余输入星型数据属性的恒星。第二个现有研究表明[30.,31日)的拓扑结构是由分析发现锚定并遵循减少不连续中间结果的关系。第三个实证研究(32)是我们以前的工作对静态知识图的子图匹配,基于流的子图构造了一个索引来减少冗余RDF数据。

受益于之前的研究,dominance-partitioned子图模式的目的是封装的拓扑图形和属性的结构模式。然后,大RDF图可以分割的援助dominance-partitioned模式子图,并介绍了分区RDF图的框架详细第三节。

3所示。框架Dominance-Partitioned RDF图

在本节中,一个dominance-partitioned子图匹配框架提出了对大数据进行查询图的子图映射图。首先,dominant-connected模式从一个模式获得的图是图。其次,大数据图分区是基于模式谱聚类的方法。最后,在分区的查询图的子图映射数据图进行迭代。

DP-SM的伪代码描述的算法1。dominant-connected模式子图(简称DCPG)从一个模式获得的图 ,这是形成 。首先,模型流图被用来提取主导模式的顶点和支配关系图。然后,是由顶点和支配主导模式的关系图(1和线3.1节)。其次,谱聚类的方法是用来把大基于超图的数据图(2行3.2节)。最后,查询图的子图映射问在分区的数据图进行迭代(3和行吗第四节)。

3.1。占主导地位的模式连接图

dominant-connected模式子图指的是图的子图模式 ,令人满意的⊆ ,这是扩大从统治者树的理论33]。考虑图模式和顶点u,u′∈ ,如果存在一个人为设计的根u_r∈ ,这样u是一个必要的顶点的路径u_r来u′,然后u是一个主导节点的u′,形成u≺u′。类似于查询顶点之间的支配关系,如果存在一条边e的 ,令人满意的e是一个必要的边缘路径u_r来u′,然后e≺u′。支配关系的基础上 ,占主导地位的模式连接图的定义中描述的定义5。

定义5(显性连接模式子图)。给定一个图模式和一个根节点u_r∈ ,子图模式是一种dominant-connected模式子图,形成 ,当且仅当它满足条件:(1)对于任何一个节点u′∈( ),它总是找到一个节点u∈这样u≺u′的路径 。(2)对于任何优势e′∈( )和结束节点u′的e,满足e≺u′的路径在哪里从根节点的路径吗u_r查询顶点u′。主导的关系u≺u′和e≺u′上请参考,u和e是必要的顶点和边的路径u_r来u分别′。我们定义主导节点的收集器作为 ,然后,它满足条件⊆⊆ ,组节点由u被表示为一组主导的吗u,形成dom(u)。
考虑图模式和一个人工根节点u₁在图4(一),的如图4 (b)。用于收购的支配关系拓扑和属性结构模式的图;因此,模式的方向性图无法计算的 。考虑到在图4 (b),如果任何一个节点的被删除,这样吗是无效的,那么是最低的。关于删除节点u₃令人满意的边缘(u₆,u₃)和(u₂,u₃)也被删除 ,然后将是无效的,因为找不到优势主导u₃在 。
在本文中,我们探索的特点分析节点外延和内涵图模式的关系 。节点发现外延关系模式的控制顶点的关系图,所述定理1。

定理1(节点外延关系)。给定一个DCPG ,如果存在一个主要节点u∈ ,令人满意的dom(u非空的,然后,节点dom(u)构造一棵扎根u。

证明。(定理1)。一组占主导地位dom(u)被认为是令人满意的u是一个必要的顶点的路径吗 ,因此dom(u),u可以组合成一个流图来自u.Different边缘e,e′∈被认为是,如果共同结束节点u′包含他们e和e′并不占主导地位的边缘u′。nondominating顶点和边之间的关系与条件(2)的定义5。
节点发现的内涵关系是顶点semidominant关系图模式。一个DCPG 和一个控制顶点u∈被认为是,如果存在一个占主导地位的顶点u的道路上 ,令人满意的u≺u′,这样d(u_r,u′)的最小距离D(u_r,dom(u_r,u′))u是一个semidominant节点的u′,形成u≼u′。在这里,dom(u_r,u′)是一组顶点主导u′的路径 ,d(u_r,u′)表示的距离u_r来u′,收集到集D(u_r,dom(u_r,u′)),令人满意u′∈dom(u_r,u′),d(u_r,u′)∈D(u_r,dom(u_r,u′))。中定义的节点内涵关系定理2。

定理2(节点隐含的关系)。给定一个最小DCPG ,如果存在一个主要节点u∈semidominated由u′∈ ,然后的路径u′,u结合节点或单圆图或multicircular图。

(定理证明2)。最小DCPG指DCPG生成至少主导模式的节点图。DCPG 被认为是,如果存在主导节点u∈semidominated由u′∈ ,令人满意的路径u′,u,然后,必须存在一个小DCPG不包含u,从而不是一个DCFG最小。因此,如果u′和u是不同的主要节点,必须存在多条路径的u′,u,这应该作为单圆或multicircular图相结合,否则,他们是常见的主要节点。

3.2。Dominance-Partitioned模式超图

在本节中,dominance-partitioned模式超图的方法(简称DPPG)是第一个构建主导节点和控制关系。然后,dominance-driven谱聚类的方法被用来划分图作为一个模式k子图。dominance-partitioned模式超图中定义的定义6。

定义6 (dominance-partitioned模式超图)。给定一个最小DCPG ,DCPG dominance-partition模式超图是一个超图,形成 在哪里是一组主导节点和⊆×表示一组边缘。
hypernodes和hyperedges DPPG表示模式的几何图形 ,节点的基础上所进行的外延和内涵的关系 。
节点的几何是一个有子图 。一套控制dom(u)被认为是,我们定义的外延和内涵的关系u作为一个树各种子图和圆形组合子图 ,分别。枝状的组合子图和环形阵列控制节点的子图u表示为(u)。因此,(u)是一个有图semidominant节点(u)的鱼头和树叶(u),鱼尾巴。边表示的几何圆形组合常见的子图,这是由任何主导节点之间的多条路径 。
考虑到模式图和dominant-connected模式子图在图4,dominance-partitioned模式子图见图5,轮充满对角线表示的主要节点,和轮充满垂直线表示semidominant节点。每个dominance-partitioned模式子图由semidominant节点的多条路径的主导,主导节点的树的形状结构为主。关于dominance-partitioned模式子图(u),它是由多个路径 从u₁来u₃和主导树状结构{u₃,u₄,u₅}。
因此,k分区图模式问题可以转化成鸿沟k超图的子图 ,用定义表示是哪一个7。

定义7 (dominance-drivenk分区问题)。给定一个dominance-partitioned超图模式 和= {u₁、…u_n},dominance-drivenk是指除分区问题成k集群,满足C= {C₁、…C_k},重叠的成本 子图和最小成本满足条件
在哪里表示pattern-clustered子图的成本和 表明pattern-clustered子图的重叠的成本 ,…, 。
在本文中,我们使用缩写词( )作为 。然后,重叠pattern-clustered成本重新定义为子图 ,和子图成本表示为 |。在这里,对应于我th的集群C_我。实际上,重叠的成本相当于 ,在引理证明1。

引理1(节点隐含的关系)。鉴于pattern-clustered子图和 ,重叠的成本相当于 。

证明。(引理1)。Con年代我der在g the node denotative relationship in Theorem1,关于主导节点u∈和u′∈ ,如果存在(u∧)≠∅,然后u≺u′或u′≺u。关于控制的关系u′≺u必须存在一个semidominant节点u“≺u,这样u“≺u′或u”=u′。考虑节点的内涵关系定理2,u′必须包含 。因此,(u∧)≠∅。

3.2.1之上。Dominance-Pattern加权矩阵

dominance-pattern加权矩阵模型的相似性pattern-partitioned子图通过其双向邻接矩阵的大小n×n,在那里n=和表示一组主要节点。此外, 代表了子图的成本和 代表之间的重叠的成本和 , 当且仅当≠0∧≠∅,否则 = 0。

pattern-partitioned子图的子图成本评估的三元组映射到模式三元组的数据量。一个pattern-partitioned子图(u)被认为是和子图的成本(u)是数据三元组映射到所有三元组模式的数量(u),形成 。Pattern-partitioned子图和被认为是,重叠的成本是成本的常见的子图子图模式,形成 。描述的子图和重叠的成本以下公式:

3.2.2。K分区在Dominance-Pattern加权图

的k分区用于图形DCPG切成k子图不连接到对方。我们定义的设置k主导节点作为C₁、…C_k,满足C_我∩C_j=∅C_我…C_k= ,1≤我,j≤k。

对于占主导地位的节点集C_我和C_j任何模式的子图和 ,我们定义之间的图上的重量C_我和C_j如以下公式:

因此,对于主导节点集C₁、…C_k的k子图模式 ,图上的重量k图形模式定义为下面的公式: 在哪里是互补的 ,令人满意的 。

3.3。Dominance-Partitioned算法在大型RDF图

在本节中,k-partition算法是用来把大数据图multiple-distributed子图。我们第一次给DPPG的构造算法2然后,dominance-driven k-partition设计算法3。

第一个DPPG建设的核心工作是选择一个模式的根节点图。凭直觉,我们倾向于选择最小的节点本地匹配结果和最大程度作为根节点。查询顶点进行最小的匹配结果意味着最小的网络传输成本,和最大程度的手段最大概率修剪-节点对。根节点的计算公式中描述以下方程: 在哪里米(u)表示实体类型和原因u,满足米(u)∈ 。W3C组织提供了一组词汇(如RDF标准的一部分)在RDF图编码丰富的语义信息。例如,类型谓词(rdfs: type)提供的功能分组RDF图的顶点分成不同的类别。不同于一般的标签图,RDF图的顶点识别实体/文本信息,和实体的语义特征导致相同类型的顶点通常有类似的谓词组合,方便统计。因此,实体的可以很容易地映射到模式的节点通过输入和自己认为实体上的谓词。

建设DPPG算法所示2。输入是一个模式的图 ,和输出是一个超图dominance-partitioned模式 。一个人工根节点首先是由公式(5)。根节点u_r是由一个初始编码顺序号码DFS (u_r)= 0和添加到主要集(1号线),然后按顺序执行的四个模块DPPG建设。

第一个模块是编码顺序独特的每个顶点的数量通过深度优先搜索的顺序(2 - 6行)。每个节点u的编码迭代通过搜索访问节点的继任者u_r(2)行。如果u既无,u编码的继任者u部署到编码器(3 - 4行)。如果u访问,u作为一个主要节点添加到主要集(5 6行)。

第二个模块是确定的semidominant节点降序排列的深度优先搜索(7行)。每个节点u′的在搜索迭代地进行追踪编码节点的前兆吗u(第8行)。如果DFS (u)< DFS (u′),边缘(你,你′)被收集到一个圆形组合子图的前体u′是部署到示踪(9 - 10行)。如果DFS (u)> DFS (u′)},sdom(u]>sdom(u′),的semidominant节点u取而代之的是u′和边缘(u,u′)被收集成圆形组合子图(11 - 12行)。

第三个模块是最小化的主导(13 - 16行)。考虑主要节点u∈ ,如果存在一个节点u′∈−u,满足DFS (u)< DFS (u′)< DFS (sdom(u]],然后u′从 。

第四模块获得DPPG dominance-partitioned模式子图()17 - 21行区间。一个节点的主要节点u添加到树各种子图(u),联盟(u)和(u更新)(u)(17 - 18行)。考虑dominance-partitioned模式子图(u)和(u′)如果(u)∧(u′)≠∅,hyperedge (u,u′)构造 。

3.3.1。例子DPPG建设

DPPG建设见图的一个例子6,轮充满对角线表示主要节点和轮充满竖线表示semidominant节点。

根节点是第一选择u₁由公式(5),它应该包含与最小的地方匹配结果和最大的程度。然后,四个模块在DPPG建设顺序执行。编码顺序的第一个模块是独一无二的每个顶点的数量通过深度优先搜索的顺序。顺序唯一的下标数字编码节点,和双访问节点收集一套主导 ,令人满意的= {u₃,u₆,u₉,u₁₅}。

第二个模块是确定的semidominant节点降序排列的深度优先搜索和semidominating关系获得为{u₁≼u₃,u₁≼u₆,u₇≼u₉,u₁≼u₁₅}。semidominating关系在收购过程中,环形阵列边缘插入圆形组合子图。关于一个主导节点u₃的前体u₆的u₃满足DFS (u₃]}< DFS [u₆]},因此前兆u₆应该不断扩大,(u₆,u₃)插入 。后的semidominant节点u₃被发现是u₁,提升路径插入(u₃)。dominance-partitioned模式子图见图6。

第三个模块是最小化的主导。考虑主导节点u∈ ,如果存在一个节点u∈− ,令人满意的DFS (u)< DFS (u′)}< DFS (sdom(u]],然后u′从 。第四模块获得DPPG dominance-partitioned子图模式。树状结构为主结合圆形组合子图,用于进行紧凑dominance-partitioned子图模式。

的dominance-driven k-partition中描述的算法3。输入是一个dominant-connected图模式 和RDF图 。输出是一组k分区数据子图 。的dominance-drivenk分区算法包括三个模块。

第一个模块是构建一个类似矩阵的dominance-partitioned模式超图(1 - 4行)。dominance-pattern加权矩阵初始化的相似性pattern-partitioned子图通过其双向邻接矩阵的大小(1号线)。 代表了子图的成本(3)行 代表之间的重叠的成本和(4号线)。

第二个模块是通过积累程度来计算矩阵元素相似矩阵的每一行(5 - 6行)。然后,图拉普拉斯算子的方法被用来计算特征矩阵,令人满意l= ( )和f^T低频= 。因此,相似矩阵可以抽象为一个特征矩阵F的大小 (第7行)。此外,ak聚类方法则是用来收集特性矩阵逐行k集群(第8行)。

最后,第三个模块是生成k分区的数据通过映射数据图的子图k集群(9 - 11行)。考虑pattern-clustered子图的集群C_我三,如果存在一个数据t∈ ,令人满意的t∈ ,然后t是一个映射数据的三倍吗(11行)。

3.3.2。例子Dominance-DrivenK分区

每个子图是作为hypernode dominance-partition模式,每条边表示共同dominance-partition模式子图之间的部分。考虑圆形组合子图(u₃)和(u₆)在图6边(u₁,u₆)是常见的部分(u₃)和(u₆)。关于dominance-driven 3-partition战略、集群模式子图见图5。RDF图和图模式被认为是数字1和2图划分模式和分区RDF图见图7。子图划分模式(=(部门)),(=(GraduateCourse)如图7(一),在那里和普通节点都有模式子图semidominated吗ResearchAssistant。关于dominance-driven 2-partition策略,划分模式子图不需要集群,因为集群模式子图仍然是分裂的。大型RDF图划分为不同的服务器基于子图划分模式和 ,所示的数据7 (b)和7 (c)。

4所示。子图匹配k分区的RDF图

在本节中,我们介绍了子图匹配算法上k分区的RDF图。给定一个查询图问和一个数据图 ,子图匹配问题是指搜索所有同构的子图问在 。在这里,查询图被定义为子图的 ,形成问( )。

4.1。支配关系的可行性

流动特性对应一个模式的图在这篇文章中,我们用一个虚拟根附加查询图人工同位素的根u_r模式的图。root-attached查询图重新定义 ,在哪里就是虚拟根节点。给定一个图模式( )和一个人造的根u_r查询,如果存在一个精致的图 ,令人满意的u_r∈ ,然后u一个非空的节点和′u_r= ,否则,u′是一个空节点。考虑到精制查询图问₁和问₂在图8(一个)、节点u₁的问₁是一个真正的根节点的图在图吗9和节点u_r的问₂是一个虚拟的根节点是同位素节点u₁。确保的可达性问₂,虚拟构造边缘u₂到最近的节点u₁和u₇在可获得的路径u₁在图9。

支配关系图模式仍适用于精确查询图,证明的定理3。

定理3(的关系)的可行性。给定一个图模式和查询图 ,如果存在节点u,u′∈∩ ,令人满意的u≺u′在 ,然后控制关系u≺u′仍然是合适的问。

证明。(定理3)。我们使用矛盾证明支配关系的可行性。考虑图模式和查询图 ,如果存在节点你,你′∈ ∩ ,令人满意的u≺u′在 ,这样的关系u≺u不能适合′问。然后,一定存在另一个节点u”,令人满意的u”是可及节点的路径 。自是同位素u_r的 ,u“必须可及节点的路径 。然而,u不会占据主导地位u′在 ,因为存在两节点u和u”,可及节点的路径 。
关于改进查询的图表问₁和问₂在图8,查询图继承模式的支配关系图,因为它总是可以找到一个查询根节点(真实或虚拟节点),同位素模式的根节点图任何查询图。
受益于支配关系定理的可行性3计算模式的组合,子图匹配和DCPG的概念可以进行许多杰出的特性加速RDF图的子图匹配。子图匹配的最小计算单位是一对数据查询顶点(节点),描述的映射查询顶点u顶点数据 ,形成 。子图匹配的溶液被定义为子图映射,形容 ,n= 。一个DCPG-based特点是用引理表示2。

引理2。给定节点对 和 在子图映射米,如果存在一个虚拟节点 ,令人满意的u≺u′上 ,然后≺在 。

证明。(引理2)。关于子图映射 的问在 ,它必须满足边缘约束的子图同构的定义2:∀u,u′∈ ,∃(u,u′)∈E_问:(米(u),米(u′)∈E。因此,考虑节点对 和 在米如果存在支配关系u≺u′,(=米(u)必须占据主导地位(=米(u′)根据边缘约束的传递性。
进一步说,一个有趣的特征可以从正面和负面的节点对开采。一对节点被称为作为一个积极的节点对当且仅当它满足候选人验证,所示的定义8。

定义8(候选人验证)。一对节点 是正当且仅当它满足以下约束条件:(1) ,(2)∀u′∈N(u), ,和(3)∀(u,u′)∈E_问,
在哪里分别表示顶点和边的标签功能,代表了vertex-label加上顶点u和l_E(u,u′)代表了edge-label设置加上边缘(u,u′)。

引理3。节点对占主导地位的 不能进行任何一个包含子图映射 如果 是负的。

证明。(引理3)。一个消极的节点对 被认为是,它不满足约束的子图同构的定义2,从而米(u)≠ 。此外,由节点对 不能进行任何一个包含子图映射 。
因此,我们首先使用一个圆形组合匹配以指导子图匹配的迭代处理。考虑提炼查询图问₁包含一个真正的根u₁在图8(一个)环形阵列的节点(u₁₅)是第一个命令子图匹配的过程。考虑提炼查询图问₂包含一个虚拟根u_r在图8 (b)节点的圆形图案和第一个命令在子图匹配的过程。自问₂包含两个圆形图案,它需要执行多个圆形图案(选择一个优先考虑的u₉)和(u₃)。优先选择多个环形阵列的密度的圆形图案,形成的一个顶点在一个圆形组合比例的优势。对于圆形图案(u₉)和(u₃),计算密度为1和2/3,那么(u₃)前执行(u₉)。注意,密度的计算没有考虑虚拟根和边查询图加上虚拟根,类似问₂。

4.2。物理存储

我们设计的RDF图的物理存储加速triple-based RDF数据的采集。之前我们的物理存储的引入,字典编码映射表首先设计编码RDF三元组为整数的字符串。

字典编码映射表包含数据和语义词典。数据字典对应instance-labels RDF三整数独特的数字和语义词典对应谓词,type-labels, attribute-labels RDF三整数独特的数字。

考虑到RDF图在图1、语义和数据字典表中所示2。数据和语义词典由两部分构成:第一部分记录的整数编码(例如, 。)和第二部分记录instance-label、谓词类型标签或attribute-label(例如,Person_A,advisorBy)与独特的整数编码的第一部分。的v-id每行代表一个数据字典,封装了一个独特的整数和instance-label(例如, )。语义字典表的显示p/类型/属性,每一行封装了一个独特的整数和一个谓词或类型标签或attribute-label(例如, , ,和 )。

关于数据的划分RDF图7 (b)和7 (c),我们的物理存储显示在图10,采用哈希映射表的结构布局。的关键形成(v-id|p/类型|dir),价值被分配为p/类型,在那里v-id是一个独特的整数编码,p/类型代表一个谓词或类型标签或attribute-label,和dirRDF三的方向图。例如,一个关键(1 | 0 | 0)服务器1指in-edges顶点编号为1的标签,这是谓词advisorBy标记为1。一个关键(1 | 8 | 1)表示顶点编号为1的类型标签,标签FullProfessor标记为10。的关键[0 | | 8 0]表示顶点加上一个标签在边缘rdf: type标记为8,Person_A,Person_B,Course_A,Course_B,标记为1、2、6和7,分别。

4.3。物理存储

的子图匹配k分区RDF图中描述的算法4。输入是一个查询图问(u′_r, , )和输出的子图映射ℳ问在 。

子图匹配算法是原始的直到所有子图进行映射。数量我用于计数进行积极的节点对,子图映射ℳ如果相当于(1 - 2行)。环形阵列的第一匹配顺序是用来指导迭代处理子图匹配的前题2和3。一个同位素的虚拟根附加到原始查询图和分配给一个初始号码吗我=−1(4号线)是一个虚拟节点的接班人扩大探索真正的节点对(第5行)。

迭代处理插入的节点对ℳ(7 - 11行)。考虑选择查询顶点u_我节点对u_我是以前从(第7行)。如果节点对 是积极和满足局部子图同构, 扩展ℳ和继任者的u_我扩大探索读节点对。否则,其他节点顺序对部分验证了子图同构和候选人验证(8 - 10行)。如果查询的节点对顶点u_我是负面的或不满足局部子图同构,的前兆吗u_我出尔反尔,重复进行处理,直到所有子图映射扩展到ℳ(11行)。

4.3.1。为子图匹配算法示例

在子图匹配算法中,我们使用一个圆形组合第一次匹配以指导子图匹配的迭代处理。一个命令查询图如图11,轮充满left-diagonal线表示第一个执行地区,轮充满right-diagonal行显示第二个地区,执行和nonfilled轮指最后的地区执行。满轮都包含在圆形组合子图u₇是该地区的时刻。然后,子图匹配是我们圆形组合迭代由第一个匹配的订单。

5。实验评价

在本节中,我们验证算法的有效性和可伸缩性合成和真实数据集上进行实验,实验,我们主要分析当前基于内存分布式SPARQL查询处理策略。

5.1。实验设置

所有的实验都进行分布式集群包括六个相同的计算节点。每个计算节点使用一个英特尔(R) (TM)核心i7 - 7700 @3.60 GHz 8核处理器,和节点通信是部署在1000 Mbps的以太网。16 GB的物理内存,硬盘的大小是1 T。

实验评价采用合成数据集的生成四个尺度LUBM(利哈伊大学基准)和实际数据集YAGO2(另一个伟大的本体2)。数据集的相关信息如表所示3,#T,#年代,#O,#P代表三元组的数量、主题、对象,分别和不同谓词。

5.1.1。数据集

合成数据集LUBM [34)是由利哈伊大学,这是一个标准和系统的语义Web大学本体库评价基准。这个基准测试旨在评估一个真正的本体的扩展查询大量数据集。这两个不同大小的数据集数据生成器生成的非洲联合银行1.7 \{脚注http://swat.cse.lehigh.edu/projects/lubm}。YAGO2 \{脚注http://yago-knowledge.org}是一个关联数据知识库,主要集成了数据从三个来源:维基百科,WordNet, GeoNames包含1.2亿三元组和1000万多个实体(如个人、组织和城市)。

5.2。实验结果分析

我们比较我们DP-SM算法的查询性能与三合会(4和悟空5]。查询表演6个计算节点上部署(包括一个主节点)和评估lubm - 2560数据集。基准用于生成不同尺度的查询图,这是受雇于许多分布式RDF系统的研究,发表在12]。

实验评估分成两组的查询图,见图12。第一组的查询图L1、L2和L3对应于Q1,第三季度,迄今为止,分别在19),我们的PD-SM算法比悟空算法更快的1.4 - -2.2倍。实际上,L2的最终结果是空的。虽然存在大量的查询谓词关系映射到图形L2,核实候选人的查询节点是空的。候选人确认之前我们的算法可以找到所有查询节点之前的候选人匹配执行处理,而悟空的算法和三合会需要找到候选人耗时的遍历大型中间结果。L1和L3的最终结果是65000年和1000年数据进行子图,分别。实验验证基于勘探方法有近一个数量级的速度比特性加入模型。环形阵列的第一匹配顺序是用来指导迭代处理的子图匹配算法,可以修剪多余的中间结果。因此,我们的算法匹配的性能得到更大的改善。

查询图的第二组L4、L5和16种对应于扩展Q2, Q1, Q7 [19),它使用更复杂的比L1和密集的拓扑结构,L2和L3。L4的查询图是一个非圆形拓扑结构和中间结果是更大的没有局部子图同构的验证。因此,我们的算法DP-SM比三合会有一个小的改进。与悟空算法相比,改进的匹配算法的性能好处从笛卡尔的推迟cluster-connected计算战略产品。查询图16种包含比L5更密集的环形拓扑结构。圆形组合第一匹配策略可以加快收购子图的结果。

平均在YAGO2数据集评估在图匹配的时间13,简单的和复杂的查询图都用(表示8]。类似于实验评价LUBM数据集,复杂的查询图的匹配性能Y4,日元,日元是类似于复杂的查询图的实验评价LUBM数据集,如图13 (b)。我们DP-SM提出的算法是1.5 - -2.5倍算法悟空和三合会。所不同的是,简单的查询图的匹配time-performances Y1, Y2,和Y3速度比单纯形的LUBM数据集,因为简单的查询图的节点是有限的常量值,可以进行较小的搜索空间的中间结果,如图(13日)。相比之下,悟空和SDSM,中由于我们的算法时间消耗在匹配的编排顺序,它是与匹配算法的总体运行时间可以忽略不计。

5.3。实验的可伸缩性

算法的可扩展性是评估基于机器的数量和数据集的大小。

基于机器的数量的可伸缩性是评价图14,机器的数量正逐渐从2增加到6。实验结果表明,查询图的匹配time-performances L1, L3、L4, L5和16种递增的顺序逐步改善机器数量。实验评价的趋势证明了我们DP-SM算法能有效地在分布式环境中进行子图的结果。自从L2的候选人作为空在前面的候选人验证,验证匹配的时间显示为一个常数的趋势。对于复杂的查询L4、L5和16种,减少大小的匹配time-performances略低于的L1和L3,因为查询图跨越多个分区模式子图增加传输的时间消耗在分区RDF图。

基于数据集的大小的可伸缩性LUBM评价图15,机器是固定的数量是6。LUBM数据集的不同尺度的评估算法的匹配time-performances生成的,它位于从5.3米到346米不等。的匹配time-performances DP-SM算法可以保持近线性增长,而复杂的拓扑结构的查询图。我们的算法首先使用一个圆形组合匹配策略之前修剪冗余RDF和推迟subgraph-connected计算笛卡尔的产品。然后,部分中间结果都与略没有巨大的非圆形模式子图匹配的时间消耗。

6。结论

在本文中,我们提出一个dominance-partitioned子图匹配大RDF图。首先,dominance-connected模式图提取模式图构建dominance-partitioned模式超图,划分图模式为多个都子图模式。其次,dominance-driven谱聚类策略是用来收集子图模式到多个集群。第三,一个dominance-partitioned子图匹配算法设计进行所有cluster-partitioned RDF图的同构子图。最后,实验评价验证复杂查询的策略具有更高的效率,并在多个机器上更好的可伸缩性和不同尺度的数据。

数据可用性

LUBM数据用于支持这项研究的结果已经存入网络存储库(http://swat.cse.lehigh.edu/projects/lubm)。YAGO2数据用于支持这项研究的结果已经存入网络存储库(http://yago-knowledge.org)。

的利益冲突

作者宣称没有利益冲突有关这篇文章的出版。

确认

这项工作得到了国家自然科学基金(批准号61976032)。

引用

1. m . r . Garey d·s·约翰逊,电脑和棘手:np完全的理论指南w·h·弗里曼,纽约,纽约,美国,1979年。
2. t·纽曼和g .威库姆”Rdf-3X: RDF RISC-style引擎,”美国养老,1卷,不。1,第659 - 647页,2008。视图:出版商的网站|谷歌学术搜索
3. c . Weiss p。卡拉,a·伯恩斯坦,“Hexastore:六倍的索引为语义web数据管理、“美国养老,1卷,不。1,第1019 - 1008页,2008。视图:出版商的网站|谷歌学术搜索
4. s . Gurajada s Seufert i Miliaraki, m·西奥博尔德”三:分布式无共享RDF基于异步消息传递引擎,”学报2014年ACM SIGMOD国际会议管理的数据雪鸟,页289 - 300年,但是,美国,2014年6月。视图:谷歌学术搜索
5. j .史y姚明,r . Chen h . Chen和f·李,“快使用RDMA-based分布式和并发RDF查询图探索”第12届USENIX学报》研讨会上操作系统的设计和实现佐治亚州萨凡纳,页317 - 332,美国2016年11月。视图:谷歌学术搜索
6. l .他邵,y李et al .,“笔:一个强类型的存储为大规模的RDF数据服务,“美国养老,11卷,不。2、203 - 216年,2017页。视图:出版商的网站|谷歌学术搜索
7. 问:徐,王x, y Gan, j . Li l .柴和j·王,“StarMR:一个有效的基于star-decomposition查询处理器使用MapReduce SPARQL基本图形模式,”亚太网络学报》(APWeb)和网络时代信息管理(WAIM)联合国际会议网络和大数据澳门,页415 - 430年,中国,2018年7月。视图:谷歌学术搜索
8. x Wang l .柴问:徐et al .,“有效的子图匹配在大RDF图使用MapReduce,”数据科学与工程,4卷,不。1,24-43,2019页。视图:出版商的网站|谷歌学术搜索
9. 林f . Bi l . Chang x, l .秦和w·张,“有效的子图匹配通过推迟笛卡尔产品,”诉讼的ACM SIGMOD国际会议管理的数据,页1199 - 1214年,旧金山,美国,2016年6月。视图:谷歌学术搜索
10. j . z盘“资源描述框架”,手册上的本体施普林格,柏林,德国,2019年。视图:谷歌学术搜索
11. d . j . Abadi a . Marcus s r·马登和k . Hollenbach”SW-store:垂直分区DBMS对语义web数据管理、“VLDB日报,18卷,不。2、385 - 406年,2009页。视图:出版商的网站|谷歌学术搜索
12. t·纽曼和g·威库姆”,RDF-3X引擎可伸缩的RDF数据的管理,“VLDB日报,19卷,不。1,第113 - 91页,2010。视图:出版商的网站|谷歌学术搜索
13. l . p . Peng邹,l·陈,d .赵”自适应分布式RDF图分割和分配基于查询工作负载,”IEEE工程知识和数据没有,卷。31日。4、670 - 685年,2019页。视图:出版商的网站|谷歌学术搜索
14. 黄j . d . j . Abadi, k .任“大型RDF图的可伸缩的SPARQL查询”,美国养老,4卷,不。11日,第1134 - 1123页,2011年。视图:出版商的网站|谷歌学术搜索
15. k·Rohloff和r . e .注意力,”Clause-iteration MapReduce扩展查询datagraph碎片图库,”诉讼ACM第四国际研讨会上的数据密集型的分布式计算页,35-44圣何塞、钙、美国,2011年6月。视图:谷歌学术搜索
16. g . Karypis诉Kumar,“快速、高质量多层次方案划分不规则图形,“暹罗期刊在科学计算,20卷,不。1,第392 - 359页,1998。视图:出版商的网站|谷歌学术搜索
17. l .赖l .秦x, y, l . Chang和美国,“可伸缩的分布式子图枚举,”美国养老,10卷,不。3、217 - 228年,2016页。视图:出版商的网站|谷歌学术搜索
18. a . Schatzle m . Przyjaciel-Zablocki s Skilevic, g . Lausen”S2Rdf: RDF和SPARQL查询火花”,美国养老,9卷,不。10日,804 - 815年,2016页。视图:出版商的网站|谷歌学术搜索
19. m . Atre诉Chaoji m·j·海岬和j·a·亨德”矩阵加载:一个可扩展的轻量级的加入为RDF数据查询处理器,”诉讼的ACM 19国际会议在万维网上页。每周,罗利数控、美国,2010年4月。视图:谷歌学术搜索
20. b . p .元,p . Liu, h·金,w . Zhang和l .刘”TripleBit:快速大规模RDF数据和紧凑的系统,”美国养老》第六卷,没有。7,517 - 528年,2013页。视图:出版商的网站|谷歌学术搜索
21. l .邹j . Mo m . t . Ozsu l . Chen和d .赵”gStore:回答SPARQL查询通过子图匹配,”美国养老,4卷,不。8,482 - 493年,2011页。视图:出版商的网站|谷歌学术搜索
22. l .曾庆红和l .邹”gStore系统的重新设计。”计算机科学的前沿,12卷,不。4 - 2018页。视图:出版商的网站|谷歌学术搜索
23. b . k .曾庆红,j .杨h . Wang邵,z .王,“web扩展RDF数据分布式图形引擎,”美国养老》第六卷,没有。4、265 - 276年,2013页。视图:出版商的网站|谷歌学术搜索
24. 和l . j .徐j . Chen阴,“多目标空间和语义关键字查询:基于distance-owner方法,”分布式和并行数据库,38卷,不。3、625 - 647年,2020页。视图:出版商的网站|谷歌学术搜索
25. y元,周x, z . Wang和h .秦”有效和高效的社区搜索直接跨异构社会网络图,”31日,澳大拉西亚的数据库的程序的会议澳大利亚墨尔本,页161 - 172,,2020年2月。视图:谷歌学术搜索
26. 周x, j .徐r . et al .,“S2R-tree: pivot-based semantic-aware空间关键字搜索、索引结构”GeoInformatica,24卷,不。1,3-25,2020页。视图:出版商的网站|谷歌学术搜索
27. l . y . Cheng Chen y元,g .王”语义和有效的修复方法,基于规则的图修复:”美国第34 IEEE国际会议数据工程,页773 - 784年,巴黎,法国,2018年4月。视图:出版商的网站|谷歌学术搜索
28. y, y元,l·陈,c . Giraud-Carrier g . Wang和y太阳,“分配:分布式方法在大型不确定图可达性查询,”IEEE并行和分布式系统,27卷,不。11日,第3185 - 3172页,2016年。视图:出版商的网站|谷歌学术搜索
29. y, t·聂,d .沈,g . Yu”深聚合模型对蛋白质二级结构预测,“国际期刊的数据挖掘和生物信息学,22卷,不。3、231 - 249年,2019页。视图:出版商的网站|谷歌学术搜索
30. t . Cai, j·李,a . s .面t . Sellis r . Li和j . x Yu”Target-aware整体影响力最大化在社交网络空间,”IEEE工程知识和数据,没有。99年,p . 2020。视图:出版商的网站|谷歌学术搜索
31. t . j . Li Cai,邓k, t . Sellis x Wang和f·夏,“Community-diversified影响最大化在社交网络,”信息系统文章ID 101522卷,92年,2020年。视图:出版商的网站|谷歌学术搜索
32. j . Du y太阳,g . Li Ning, h·陈,“基于子图的子图匹配算法指数知识图,“计算机科学的前沿,2020年。视图:出版商的网站|谷歌学术搜索
33. t . Lengauer和r·e·Tarjan”发现的绝对主力军flowgraph的快速算法,”ACM事务编程语言和系统,1卷,不。1,第141 - 121页,1979。视图:出版商的网站|谷歌学术搜索
34. 郭y、z盘和j . Heflin”LUBM: OWL知识库系统的基准,”网络杂志的语义,3卷,不。2 - 3、158 - 182年,2005页。视图:出版商的网站|谷歌学术搜索

版权

版权©2020年博宁等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。