超图拓扑特性指数个性化有趣的大标签图子图查询

文摘

有趣的子图查询的目的是找到子图同构的给定查询图从数据图和子图根据他们的有趣的成绩排名。然而,现有的子图查询方法效率低下在处理大规模数据图的标签。这是由于以下问题:(i)现有的工作主要集中在未加权的查询图,而忽略查询限制查询结果的影响。(2)过多的候选子图或复杂的节点之间连接的子图候选人降低查询的效率。要解决这些问题,本文提出了一个智能的解决方案。首先,一个同形像结构图形压缩(ISGC)策略,提出了压缩类似图中的节点以减少图像的大小和避免不必要的匹配。然后,一个辅助超图数据结构拓扑特性指数(STFIndex)旨在取代原始数据图的存储和改善在线查询的效率。之后,基于边缘的分割方法标签值步(ELSV)提出了分区索引逻辑。此外,小说Top-K兴趣子图查询方法,提出了由多维过滤(MDF)策略,上界值(UBV) (Size-c)匹配和优化加入(QJ)方法来过滤掉尽可能多的虚假候选子图来实现快速连接。我们在真实和合成数据集进行实验。 Experimental results show that the average performance of our approach is 1.35 higher than that of the state-of-the-art approaches when the query graph is unweighted, and the average performance of our approach is 2.88 higher than that of the state-of-the-art approaches when the query graph is weighted.

1。介绍

近年来,随着互联网的日益普及,大量的数据与现实密切相关的实体已经生产(1- - - - - -3[],规模迅猛增长。4在各个领域。以社交网络为例,2018年,微信的月度活跃用户稳定在大约11.2亿和450亿条消息(每天5]。在2019年,Facebook官方宣布,活跃用户总数已超过24.5亿6]。作为一种高效的数据结构,标记图(7)可以更好地表达各种实体的内部连接(8)等处理大规模数据(9]。

子图查询旨在搜索所有匹配的子图同构的数据图给定查询图和有正确的标签9- - - - - -11]。它被广泛用于描述、矿山、图表和分析各种知识(12]。例如,信用卡反欺诈知识图,我们可以监视诈骗团伙通过定义诈骗团伙(子图模式)和查询。通过使用子图查询,各种社会关系的一个企业可以获取并分析从企业知识图。此外,通过使用子图查询,优秀的团队可以开采在军事管理知识图,利益集团可以搜索在社会知识图,和目标群体可以在电子商务个性化推荐知识图。

在实践中,用户更感兴趣一些匹配子图与更高级的分数,而不是整个子图查询的查询结果。通常,得分排名的子图称为一个有趣的子图,以及兴趣度计算排名得分的分数(13的子图,权重的总和。为了减少信息过载的负面影响,Top-K有趣的子图查询的概念(13),提出了选择K得分最高的子图的子图查询的结果。例如,图1(一)显示了一个数据图G从DBLP抽象,在哪些节点,J和F代表作者,期刊,研究领域,分别;每边的重量表示两个实体之间的关联程度。图1 (b)显示了一个查询图问Top-K有趣的子图查询。假设K= 2,那么Top-K有趣的子图同构问在数据图G是P₁(有趣的分数是3.4)P₂(有趣的分数是3.0)。

最近,各种方法提出了Top-K有趣的子图查询。然而,大多数现有的子图查询方法效率低下在处理大规模的图。这是由于以下问题:(i)现有的工作主要集中在未加权的查询图,而忽略查询限制查询结果的影响。(2)过多的候选子图或复杂的节点之间连接的子图候选人降低查询的效率。

具体地说,在实践中,用户经常想要更具体和准确的查询结果。这可以通过向查询添加约束的过滤器图。把图1(一)作为一个例子,对于给定的查询图问和数据图G,我们可以找到所有的同构子图问在G。然后,如果约束或过滤器添加到查询图,我们可以找到更精确的子图匹配结果查询结果,如发现团队(即。与频繁子图)成员之间的合作。这可以实现通过添加两个实体之间的边的权值与标签的查询图。换句话说,它是找到查询图的同构子图与数据图上的最高分数,和重量任意两个作者之间边缘节点同构子图是大于或等于两个作者之间的边缘重量查询节点图。发现同构子图与边的权值大于或等于的查询图称为约束或过滤器。因此,本文获得子图查询结果的过程通过约束或过滤查询图被称为个性化Top-K有趣的子图查询。它指的是K匹配子图与一流的成绩在整个查询结果与查询图同构和满足约束或过滤器。

解决上述问题,本文提出了一个智能的解决方案。具体地说,一个同形像结构图形压缩(ISGC)策略是首次提出压缩类似图中的节点以减少图像的大小和避免不必要的匹配。然后,一个辅助超图数据结构拓扑特性指数(STFIndex)旨在取代原始数据图的存储和改善在线查询的效率。之后,基于边缘的分割方法标签值步(ELSV)提出了分区索引逻辑。此外,小说Top-K兴趣子图查询方法,提出了由多维过滤(MDF)策略,UBV (Size-c)匹配和优化加入(QJ)方法来过滤掉尽可能多的虚假候选子图来实现快速连接。

我们在真实和合成数据集进行实验。的平均性能实验结果表明,我们的方法是1.35高于最先进的方法查询图是无关紧要的,和我们的方法的平均表现为2.88高于当查询图加权最先进的方法。

本文的贡献可以概括如下:(我)我们提出一个同形像结构图形压缩(ISGC)策略。具体来说,在数据图,它压缩相邻节点具有相同标签的折叠节点包含多个原始数据节点。然后,边缘连接从一个节点到折叠节点被压缩形成临界压缩边缘。压缩折叠节点和关键压缩边不仅可以减少数据图的大小,但也在批过滤器多个无效的节点和边。(2)我们设计一个索引称为超图拓扑特性指数(STFIndex),代表所有拓扑信息生成的压缩图。作为一个辅助的数据结构,它可以代替原始数据图存储。STFIndex将创建离线改善在线查询的效率。它由节点压缩拓扑指数(NCTIndex)和边缘压缩特性指数(ECFIndex),可用于过滤错误的节点和边的候选人。(3)提高计算效率的子图查询在一个大标签图,我们提出基于边缘的分割方法标签值(ELSV)步。它在逻辑上STFIndex分为多个分区,使并行查询每个分区。(iv)通过使用STFIndex,我们提出一个个性化Top-K有趣的大标签图子图查询方法,称为STF_ISQtop-k。它包含查询图预处理、多维过滤(MDF)策略,UBV (Size-c)匹配和优化加入(OJ)方法。MDF用于过滤掉尽可能多的虚假的候选人,和橙汁实现快速连接的子查询的结果。组织。本文的其余部分组织如下:在部分2介绍本文的背景下,它包含问题的陈述和相关工作。ISGC战略和STFIndex结构中讨论部分3。我们提供的细节提出Top-K有趣的子图查询方法部分4。讨论了实验结果和分析部分5。部分6是结论。

2。背景

2.1。问题陈述

数据图可以表示成一个4-tupleG= (V,E,l,W),V表示节点的集合(或点);E(⊆V×V)是边的集合;l(V⟶Σ)提出了一种函数标签节点;Σ套标签,可以出现在节点;和W边的集合。在本文中,我们研究的数据图是一个无向加权图,节点之间的无向边u和地的来标示(u, )或( ,u)。

传统的子图查询问题通常被定义为给定的查询图问和一个数据图G找到所有的同构子图问在G。爆炸的数据量和数据的复杂性,研究人员转向研究方法来搜索K优化结果通过使用边,即。Top-K有趣的子图查询(13]。然而,在实践中,用户希望能添加一个或多个约束查询图的边的权值,以满足更精确(或个性化)查询。这个查询可以被称为一个个性化Top-K有趣的子图查询。

我们使用有趣的分数(14)来确定匹配的子图的质量,重量之和的一个匹配的数据图的子图G。人们普遍认为,有趣的得分越高,更好的匹配结果。因此,个性化Top-K有趣的子图查询用于搜索K有趣的得分最高的匹配子图查询条件下,约束条件是满意。

2.2。相关工作

子图查询已经有很长的研究历史。最早的和最经典的子图查询算法,名叫乌尔曼算法(15),是基于状态空间搜索,为随后的研究奠定了基础子图查询。然而,乌尔曼算法采用递归的方法没有定义匹配的秩序。随着数据图的大小增加,乌尔曼算法的查询效率显著降低。

早在1979年,子图查询已经被证明是一个np完全问题[16,很难在有限的时间内找到最优的结果。因此,VF2 [17改进的乌尔曼的剪枝策略算法。它提出一套可行性决策规则基于最初的整数阶,然后定义的匹配顺序查询节点。然而,乌尔曼和VF2于超线性有限的大规模图的复杂性。

一些算法(18- - - - - -20.]索引构造基于频繁子结构快速匹配查询中包含的子结构图。这种方法是有效的,当查询图通常是结构。因为相同的节点或边缘可能存在多个频繁子图,挖掘频繁结构不当会导致过度冗余存储在构建大规模图索引。此外,如果查询图不包含频繁子结构,只有普通的查询方法。换句话说,频繁子图索引限制算法的通用性。

GraphQL [21]和SPath [22]构造索引基础上可获得的邻居,他们修剪的候选集通过捕获信息的邻居节点或边缘并定义相应的优化策略。GraphQL [21)利用邻居节点的信息和广度优先搜索减少候选集,它过滤掉无效的节点和边。SPath [22]构造指数D-hop范围内节点的最短路径。该指数包含的数量每跳邻居标签,每个标签对应节点的ID。前者是存储在内存速度,而后者是存储在内存或内存不足,根据该指数的大小。GraphQL和SPath未定义的匹配顺序和重复的问题等效节点的枚举。

CFLMatch [23)推迟了笛卡儿积操作减少中间结果的子图匹配。它建立了一个紧凑的路径索引(CPI)根据查询实时图来实现查询匹配。邻接矩阵表示法CFLMatch使用|(大小V|×|V|)的数据图有限,它只能用于处理小规模的数据图。塞西(24)利用BFS-based过滤和reverse-BFS-based细化修剪无前途的候选人,然后取代了边缘与设置交叉验证加快验证候选人。此外,类似的算法包括文献[25- - - - - -28]。

大多数基于索引算法采用过滤查询图中的节点的原则,和只考虑结构当前节点及其相邻节点之间的关系。他们忽视了相同的标签的节点之间的关系类型,导致大量的重复计算。TurboISO [29日]提出了梳/烫战略,使用社区等价类来生成每个NEC在子图同构的组合搜索。类似的查询图中的节点会结合成一个supernode。安排所有可能的枚举,只过滤出错。

BoostISO [30.)集中在节点之间的特征。它不仅考虑查询图中节点之间的关系,还扩展数据图的压缩技术。它还合并相似的数据图中的节点。当TurboISO BoostISO图形压缩技术应用于子图查询,他们专注于类似的冗余节点,而忽略不同节点的冗余。子图查询算法基于ASSG模型(31日)提出了(31日压缩数据图成图,可以适应的结构查询图。它减少了匹配过程的计算。然而,对于加权图的子图查询,这些算法包含一个重量过滤策略。这导致低效的过滤过程,后期否定先前查询的好处。

SumISO框架(32)进行图像压缩与模块化分解。压缩图包含查询图解析成几个区域,利用supervertex选择寻找可能匹配查询的模块图。然后,回溯算法(32)被用来在每个地区找到成功匹配的查询图。多个迭代的回溯算法很难扩展到大的图。

Top-K有趣的子图查询主要包括两部分:一是找到所有匹配的结果数据图,这是给定的查询图同构。另一种方法是先提取K子图根据权重的总和数据图。个性化Top-K有趣的子图查询添加查询给定的权重限制的查询图。

RAM (33)构建SPath索引结构并提出filter-validation策略,可以获得所有匹配的子图。然后它提取了K最有趣的匹配结果。自从获得所有匹配的结果的过程比较费时,效率低下的查询在大规模的数据图。不同于RAM读写存储器(13排名]提出的想法与匹配。Top-K有趣的子图查询的定义首先是标准化在读写存储器。它提出两个索引结构,图拓扑指数和最大metapath重量指数。还提出一个优化过滤策略过滤明显不满意的结果。读写存储器不需要排序和筛选,有效地提高了查询效率。

Top-K搜索框架提出了明星在34),由两部分组成:一个快速Top-K明星查询算法和组装算法对于一般图的查询。这是有效进行处理查询图没有重量。在[35),一个新的图形相似性度量Top-K图介绍了基于子树模式相似性搜索。它创建层次代表矩阵的快速搜索。DSQL [36)是一个分级算法近似保证,提出了寻找K子图同构与最大覆盖给定查询图。然而,它只适用于未加权的图表。TKG [37)提出了寻找Top-K频繁子图。它开始寻找模式使用一个内部度阈值设置为0,逐步提高阈值模式被发现。它有一定的局限性,它只搜索频繁子图。

PBSM [38)图像压缩技术引入Top-K有趣的子图查询减少枚举。在过滤阶段,它减少了内存只考虑成本的直接邻居。在验证阶段,花了顶点的最小数量的候选人在查询图中顶点的顶点开始匹配顺序和排名的想法而使用匹配(读写存储器)终止执行算法尽可能早的估计权重的上界。这可以减少多余的验证和提高整体性能。在[39),提出了两种类型的兴趣度度量IE-Match查询语义和基于加权的比赛。此外,它设计了一个空间索引方案DVI改善索引和候选生成过程。

CSEA模式(40)向用户提供一组特殊的属性值在顶点的一个子集。提出了模式语言的力量撒谎在其独立性的概念支持评估模式的兴趣度。只有应用于将子图没有重量。W-Gaston [41)提出了修改加斯顿算法的支持。提出有趣的方法综合频率,页面持续时间、有趣和熵参数挖掘频繁子图。

3所示。数据图压缩和STFIndex创造

本节讨论了离线数据图技术进行预处理。我们设计一个同形像结构图形压缩(ISGC)策略压缩连接节点相同的标签和边缘。然后,基于生成的压缩图,我们创建STFIndex捕捉查询图的候选人。为了扩展方法的大型图表,STFIndex分为几个分区并行处理基于ELSV分区原则。

3.1。同形像统计图结构图像压缩

结构配置文件是一个重要的XML文档数据压缩模型最早,旨在简化XML文档树结构的描述。XML结构概要文件也是一个树结构,和它没有节点相同的标签和路径。缩小的尺寸图和加快查询,本文介绍了XML结构概要文件压缩成数据图的概念,提出了一个同形像结构图形压缩(ISGC)方法。具有相同标签的节点和连接到对方被称为等效节点,以及它们之间的边缘被称为同形像的边缘。图中被称为非等效的节点,其他节点和其他边缘被称为异型边缘。

ISGC旨在合并等价节点数据图的等价关系。本文依据判断是否节点是等价的基于图的结构和节点的标签,也就是节点是否有相同的标签和被连接图。在合并的过程中等效节点,合并后的节点称为折叠节点和内部连接在一个折叠节点内部边缘。边缘之间的连接的节点合并,对一些节点内部节点折叠节点合并。合并后的边缘被称为临界压缩边缘,它的重量是内部边缘的最大重量。区分折叠节点从nonfolding节点,我们设置的第一个折叠节点id在0。我们所说的压缩图在超图,里面没有同形像的边缘。

图2显示了图像压缩的例子。其中,u₁和u₂按压成折叠节点u₀₁和关键的压缩边缘是(u₀₁,u₆0.3)。图3显示了超图G_C的数据图G在图1,折叠的节点被标记成红色。

3.2。STFIndex创造

为了提高无效节点和边过滤的效率,本文提出了一种多层索引结构,即超图拓扑特性指数(STFIndex)。STFIndex由压缩节点的拓扑指数(NCTIndex)和边缘压缩特性指数(ECFIndex)。NCTIndex可以检索信息的节点来过滤无效节点拓扑结构不符合约束条件。ECFIndex指数可以用来过滤虚假边缘候选人基于边缘的类型和重量。

3.2.1之上。NCTIndex

发现拓扑属性类型的标签和信息等相邻节点有不同的标签符号和标记的图形。因此,NCTIndex设计是基于他们在这篇文章中,这是由三层组成。

底层指数是通过超图中的节点的拓扑关系,这是一个multituple的<n_id,全国矿工工会_lable1,全国矿工工会_lable2、…全国矿工工会_lablen>。其中,n_id是id每个节点,每个节点的下标u,全国矿工工会_lable1,全国矿工工会_lable2、…全国矿工工会_lablen代表相邻节点与每个标签的数量,分别。创建中间层指数根据节点的拓扑关系包含在折叠超图的节点。它由一个4-tuple <f_id,数,max-w,孩子[]>;其中,f_id是id折叠的节点,它的下标是折叠节点u,数代表节点压缩折叠的节点的数量,max-w内部边缘的最大重量,孩子[]是底层的指针。顶层指数是根据标签创建的类型和节点的数量,由<标签类型的节点,节点与当前标签的数量,和指针的中层或底层>。底层的指针将指向unmerged节点。

例如,图4显示了NCTIndex超图G_C在图3。在顶层,我们可以看到G_C有三个类型的标签,J, F,含有3,4,4个节点,分别。层,中间为标签,它包含两个折叠节点的ids是03和04。折叠节点03由四个节点合并,和最大重量是0.9。底层存储原始节点和其相邻节点的数量不同的标签。

3.2.2。ECFIndex

标记图的特征分析,发现节点不仅包含大量的信息,但也边的信息如边缘类型(由节点标签)的组合和体重有助于筛选候选人。因此,为了进一步过滤无效的结构,本文提出了ECFIndex。它将被分为同形像边压缩特性指数(I-ECFIndex)和异型边压缩特性指数(H-ECFIndex)根据标签类型的端点是否相同。

I-ECFIndex包含一个二级指标。底层指数代表了边缘信息对于每一种类型,它是由<id₁,id₂,>,id₁和id₂是id年代的端点。提高过滤速度,底层索引存储在权重降序排列。顶层索引创建根据标签类型的边缘。

H-ECFIndex由一个三级指标。底层指数是用于建立边缘信息包含在每个标签类型,这是由包含<id₁,id₂,>。也是存储在权重降序排列。根据在折叠压缩边缘节点的特点,中间层指数包含边的端点,折叠节点的最大重量,底层的指针。它是由<id₁,id₂,马克斯- - - - - - ,孩子[]>。按照标签创建顶层索引类型的边缘。如图所示,数据5(一个)和5 (b)I-ECFIndex和H-ECFIndex超图的是什么G_C在图3。

以来的所有信息数据图可以读取的索引的底部STFIndex(包括NCTIndex和ECFIndex),构建了离线。为了避免冗余存储,可以倾倒或删除原始数据图要求,有效降低了内存开销。STFIndex空间的复杂性O(|E|)E边的集合。STFIndex产生更高的空间成本由于节点信息的复制,但它加快了过滤过程。STFIndex创造的时间复杂度O(|E|)。

3.3。STFIndex分区

为了充分提高计算效率加权图子图查询在一个大的,我们把STFIndex分成几个分区,该分区的原始数据图间接地实现并行查询每个分区。

首先,我们介绍了概念标签边缘值(ELSV)步,和标准化的定义是定义如下。

定义1。边的标签值(ELSV)步:给定一组标签的图G,l={l₁,l₂、…l_n}(n是一个正整数),自定义设置标签的顺序l,如l₁>l₂…>l_n其中,“>”表示顺序的标签,等等l₁>l₂表明l₁之前l₂。然后,ELSV边缘的标签l_我l_j(我和j是正整数)如下: 在子图匹配的阶段,许多边缘标签类型包含在数据图直接决定迭代匹配层。为了使匹配层均匀地分配到每个分区,分区方法提出了基于ELSV原则。在现实复杂的网络,如军事管理网络,社交网络,等等,边缘的大小通常是几次节点大小,甚至高出一个数量级。因此,考虑到复制的内存开销,我们把指数基于节点,需要复制NCTIndex的部分节点信息,而不是大量的边缘信息。
ELSV分区方法的主要思想是计算排序ELSVs数据图和为每个标签设置一个分区。NCTIndex划分根据标签类型的节点逻辑。例如,如果有四个标签a, b, c和d的数据图,然后我们将NCTIndex划分为4个分区,分别NCTIndex_a, NCTIndex_b NCTIndex_c, NCTIndex_d。ECFIndex, I-ECFIndex分为分区的端点。H-ECFIndex垂直分为分区根据ELSVs的平价。如果ELSV是奇数,它存储在端点小标签值的分区,如果是偶数,它存储在分区的端点与一个更大的品牌价值,反之亦然。比如如果标签的顺序是一个> > c > b d,那么标签边缘的ELSV ab是1,这是非常奇怪的。因此,我们在分区存储ECFIndex_ab b。为了保证过滤器的正确性,每个分区应该复制“特别”的信息节点从NCTIndex无需复制整个NCTIndex。“特殊”节点有相同的标签作为当前ECFIndex分区。引理1州的数量关系之间NCTIndex索引项的数量和每个分区。我们利用这个关系验证提出的分区方法的有效性。

引理1。让数据图G= (V,E,l,W),然后Num (NCTIndex_X)= Num (NCTIndex)/ 2 + 1X∈l。Num (NCTIndex_X)代表的标签数量的分区X和Num (NCTIndex)在数据图是标签的数量G。

证明。根据ELSV分区规则,认为有N标签在Num的数据图(NCTIndex)是N和标签X排名K在标签的顺序。的NCTIndex_X这是一部分,NCTIndex存储在分区X包含三个类别:(1)NCTIndex索引项的标签X;(2)NCTIndex索引项的标签排序K,ELSV是奇数,相邻节点的索引条目标签X;(3)NCTIndex索引项的标签排序后K,ELSV甚至还有索引项相邻节点的标签X。例(1),只有一个节点的标签X。(2),标签的数量K/ 2,和(3),(N−K)/ 2,然后Num (NCTIndex_X)= 1 +K/ 2 + (N−K)/ 2 =N/ 2 + 1。总之,Num (NCTIndex_X)= Num (NCTIndex)/ 2 + 1。
复制NCTIndex时,我们将只过滤和复制指数的项目NCTIndex拥有相同的标签与当前分区,而不是整个NCTIndex。因此,索引项的大小对应于每个标签分区X小于或等于原始数据图。因为Num (NCTIndex_X)= Num (NCTIndex)/ 2 + 1,每个分区的复制数量远小于整个NCTIndex。因此,ELSV分区方法避免ECFIndex的重复存储,并且极大地降低了NCTIndex冗余存储索引的开销。
此外,标签节点的频率通常是幂律分布和边缘遵循类似的模式。所以,一个标签分区的大小可能会明显大于另一个。管理分区之间的失衡,我们采用的组合逻辑和物理分区。我们使用该策略基于ELSV逻辑分区索引,然后,按分区节点和边的数目。根据集群中机器的数量,我们分配高(分区与更多的节点和边)和低级的分区到相同的物理分区,尽可能解决不平衡的问题。
把图3作为一个例子,有三种类型的节点,J和F和六种边缘AA, AJ,房颤,JJ,摩根富林明和FF。因此,我们设置三个分区,J和F NCTIndex存储节点的三种类型,分别NCTIndex_A NCTIndex_J, NCTIndex_F。我们假设标签订单> J > F,和同形像边缘AA, JJ,和FF存储在分区,J,分别和F。我们计算ELSVs异型边,这是ELSV (AJ) = 1, ELSV (AF) = 2,和ELSV(摩根富林明)= 1。ELSVs异型边的AJ和摩根富林明是奇数,所以索引项的AJ ECFIndex存储在分区J和摩根富林明存储在分区f . ELSVs与房颤甚至边缘,所以索引项存储分区的标签值较大的端点A。最重要的是,分区包含索引项ECFIndex AA和房颤,分区J包含那些关于JJ和AJ,和索引项的FF和摩根富林明存储在分区f .自从异型边标签AF分为分区,在NCTIndex_F标签的信息需要被复制在其他分区A .异型边是相似的。最后一个分区结果如表所示1S (X_Y)代表信息的节点标签在NCTIndex_X Y,和S (X)是标签的NCTIndex X。
的例子(NCTIndex_J和ECFIndex_J)分区J如图6。

4所示。个性化Top-K有趣的子图查询

4.1。查询图像预处理

有趣的子图查询之前,我们进行预处理查询图包含查询图压缩和分区,由相同的方法执行数据图。例如,查询图的压缩和分区的过程问如图7。首先,节点 , ,和有相同的标签,我们压缩成折叠节点 ,这意味着查询图问转换成超图吗问_c。然后,我们构造STFIndex问_c相同的索引条目的数据图筛选候选人的指数。最后,基于ELSV按照分区原则,问_c分为不同的分区实现后续查询。

4.2。多维过滤器

候选人的规模和精度将直接影响匹配的效率。创建有效的索引和过滤策略可以排除不一致与查询图,这可以减少不必要的验证改进子图匹配的效率。

本文提出了一种多维过滤策略(MDF)基于NCTIndex ECFIndex修剪节点和边。获取节点的候选人,NCTIndex本文用于有效地删除不符合要求的节点。我们考虑等因素的标签类型节点,折叠节点的大小,和相邻节点的数量。

基于获得的候选节点集(中枢神经系统),我们利用ECFIndex挖掘信息的节点和边。我们考虑的因素,如重量和端点的有效性进一步删除查询图。鉴于上述过滤器,我们可以获得候选边缘设置(CES),这是中间设置为后续子图匹配。我们知道大多数查询的约束限制重量,我们查询图的边缘细分成常见的边缘和特殊的边缘(权值不为零)。MDF策略五个过滤器适用于如下,(1)和(2)是用来过滤过滤了节点和边(3)- (5):(1)折叠节点位置过滤器(FNLF),对于一个折叠节点,压缩节点和一个内部边缘的最大重量必须不少于查询的图表。因此,NCTIndex用于修剪折叠节点不符合约束和过滤器的底层数据索引。同时,节点在不压缩NCTIndex都过滤掉。这是因为他们是单身节点。例如,查询图问_C_J J在图的分区7的指数数据图如图6,我们发现只有一个折叠节点有标签的问_C_J,中间层的NCTIndex标签检索获得u₀₃和u₀₄。因为压缩节点的数量u₀₄2,小于折叠节点在查询图,u₀₄和底部指数项过滤掉,u₁₁过滤作为一个单独的节点。压缩节点的数量和最大重量u₀₃都是多 ,因此,u₀₃是候选节点。(2)相邻节点标签频率滤波器(ANLFF)候选节点应该满足他们的相邻节点的数量与不同的标签不小于查询的图表。因此,基于FNLF策略,我们利用NCTIndex删除节点,不满足的发生频率相邻节点与每个标签。在那之后,我们可以获得一个更小的中枢神经系统。例如,我们可以获得的候选集 , , ,和在查询图{u₆,u₇,u₁₄,u₁₅},{u₇,u₁₄},{u₆,u₇,u₁₄,u₁₅},{u₁₂,u₁₃,u₈,u_20.,u₁₀}。(3)临界压缩边缘滤波器(CCEF),临界压缩边缘,这3.1中引入了多个边缘连接从一个节点到折叠节点合并,其最大重量不应小于查询图的重量。因此,临界压缩边缘的重量不符合约束由ECFIndex修剪,间接和底层数据过滤。由于ECFIndex底部是根据权重降序排序,我们不需要遍历的东西不到约束。因此,过滤实现批量。在我们的示例中,自( , ,0.5)和( , ,0)被压缩成临界压缩边缘( , ,0.5),和边缘的类型是AJ,我们过滤掉边缘(u₀₄,u₈,0.3)和(u₀₃,u_20.,0.4)及其相应的索引项的中间层ECFIndex,其重量不满足约束条件。(4)底特殊边缘滤波器(BSEF),为一个特殊的边缘,我们检索底部ECFIndex指数,选择具有相同标签的边缘与查询图,和重量不低于当前特殊优势。然后,我们删除虚假候选边缘的端点并不在中枢神经系统。因此,它可以进一步过滤CES上。同样的,( , ,0.5)是一个特殊的AJ边与边标签。我们检索ECFIndex_J的底部边缘候选人集合{(u₁₄,u₁₃(0.8),u₁₄,u₈,0.6),(u₇,u₈,0.5)}。(5)底常见的边缘滤波器(BCEF),为了一个共同的优势,我们还检索ECFIndex基于标签的底部索引获得边缘,具有相同的标签与当前常见的边缘,和端点都是在中枢神经系统。常见的边缘( , ,0),我们得到它的边缘候选集合{(u₁₄,u₁₃(0.8),u₁₄,u₈(0.6),u₇,u₈,0.5),(u₇,u₁₃,0.4)}。

4.3。UBV (Size-c)匹配

在本节中,匹配候选边缘设置CES上执行。我们选择最小的候选边缘设置为初始匹配边缘广度优先搜索(BFS)有效地减少迭代和计算开销。之前介绍的方法匹配,Size-c匹配的概念及其上界值(UBV)介绍如下。

定义2。Size-c匹配:它代表了部分增长匹配的时候c边缘图查询的是实例化的过程中,子图匹配c∈(1,n),n在查询图的边的数量。和有趣的分数权重的总和被实例化。

定义3。上界值(UBV):有趣的上界值在Size-c匹配分数。它等于权重的总和已经实例化和uninstantiated与最大候选边缘重量Size-c匹配的过程。
显示了匹配算法的具体步骤1。该算法保持两堆,堆Top-K堆和候选匹配(CM)。Top-K堆商店K匹配结果在降序排列。CM堆存储匹配结果以升序排序。一些比赛已经插入Top-K堆但可以覆盖后续匹配。其他比赛没有被插入到Top-K堆但是已经被证实。数组CP是用来暂时存储匹配结果,O(| E_问|)的顺序匹配(第2行)。从边缘和匹配顺序确定3 - 4行。查询图问_J被实例化的Top-K堆和CM堆在5 - 15行。如果Size-c的有趣的分数()等于或小于Top-K堆的底部,那么结果将存储在CM堆(7 - 9行)。别的,Top-K堆的底部将被复制到CM Top-K堆堆和删除,同时,结果将存储在Top-K堆(第11 - 15行)。匹配算法的时间复杂度O(n),n在CES边的数量。
候选人边缘设置CES_J图8作为一个例子K假设2。首先,我们遍历CES_J确定初始匹配边缘( , ,0.5)。然后,BFS执行从这条边的匹配顺序( , ,0.5)⟶( , ,根据匹配订单,0)。u₁₄,u₁₃0.8)被实例化( , ,0.5)获取大小是1候选人匹配(u₁₄, ,u₁₃):0.8。以此类推,Size-c增长部分匹配(c= 2…n和n查询图边的数量问_J)获得执行K匹配结果(u₁₄,u₇,u₁₃):1.2 (u₁₄,u₇,u₈):1.1,这是存储在Top-K堆。继续Top-K堆和实例化CM_J堆堆分区j . Top-K和厘米的每个分区如图9。

4.4。查询连接

一个优化加入(OJ)算法加入每个分区的匹配结果,获得完整的K匹配的查询图的子图问。它收益尽可能少的通信时间,减少沟通成本在加入阶段。之前描述的优化算法,加入引理2首先介绍了。

引理2。如果顶部K匹配结果已经加入以及兴趣度最小得分μ的有趣的分数最低的匹配导致Top-K堆分区我(Top-K_我)是μ_我。最终,顶部K匹配子图可以通过加入获得每个分区的匹配结果,其有趣的分数大于或等于 。其中,r_j,1代表第一个结果Top-K堆分区j,INT(r_{j, 1})是有趣的匹配结果r_{j, 1}(因为Top-K堆在降序排列,第一个结果是最大的兴趣度得分。),和n分区的数量。

证明。假设最终Top-K匹配子图的最小有趣的分数μ_k,从而μ_k≥μ,然后 。使 ,因此, 。因此,加入Top-K_的匹配结果我堆分区我不到是谁的有趣的分数μ_我与其他分区的匹配结果。生成匹配结果的有趣的得分将会不足μ_k;因此,它不可能是最终的匹配结果。
我们知道从引理2如果匹配结果的兴趣度最低分数分区我大于下界值 可能匹配的分区,那么说明当前分区通过加入与其他分区可能会获得更好的结果。因此,不少于的匹配结果μ_我在分区我将与其他分区更新完成Top-K结果。
橙汁的算法,查询子图包含大多数节点在初始匹配,因为它是更容易被实例化。查询订单通过BFS最初的匹配。所示的橙汁算法的具体过程的算法2。的Top-K_A, Top-K_ J,Top-K_ F每个分区的Top-K堆,CM_A, CM_J,CM_F是每个分区的CM堆。起始边缘和连接顺序确定3 - 4行。作为候选人的结果,结果Top-K_A, Top-K_ J,Top-K_ F存储在CES(第5行)。根据连接顺序,K结果计算并存储在CES Top-K_Result(第7行)。每个分区计算下界的10号线。确定是否仍有候选人在11 - 14行匹配。它继续加入新的匹配结果与初始Top-K压缩结果行16 - 19。以这种方式重复直到得到最终的结果。
把图9作为一个例子。首先,遍历CES和确定连接顺序分区⟶分区J⟶分区f .然后,查询的初始匹配结果图( , , , , , )是(u₁₄,u₇,u₆,u₈,u₁,u₉):3.4 (u₁₄,u₇,u₆,u₈,u₁,u₂):3.4,从加入Top-K成堆的每个分区,如图10。然后,计算下界值μ_我每个分区,分别μ_一个= 3.4 -1.2 -1.0 = 1.2,μ_J= 1.1,μ_F= 0.9。自从下界值都不大于最小有趣的Top-K堆对相应的分区,第一个K匹配结果返回,再次加入。因为没有匹配的有趣的得分大于3.4,每个分区不再生成一个新的结果,最终的匹配结果是(u₁₄,u₇,u₆,u₈,u₁,u₉):3.4 (u₁₄,u₇,u₆,u₈,u₁,u₂):3.4。

5。实验

在本节中,我们进行大量的实验来评估该方法使用真实和合成数据集。我们比较STF_ISQtop-k PBSM [38],IEM [39),塞西(24),和一些先进的标记图的子图查询方案。文献[39提出两种方法IEM和CM为子图查询。自从IEM的性能比厘米,在本文中,我们选择IEM的比较。

5.1。实验设置

所有实验都进行五个英特尔奔腾CPU (R) G3220@3.00GHZ机器8 GB的RAM和1 t硬盘驱动器。所有的实验都是在JAVA中实现的。每个实验重复5次,报告的平均结果。

5.1.1。数据集

我们用五种不同的真实数据集和多个合成数据集来评估我们的方法。真实数据集包括WordNet, DBLP, YouTube, DBpedia和LiveJournal上。DBLP WordNet, YouTube被用于(15,36),DBpedia用于(36),和LiveJournal被用在27]。我们获得了DBLP、YouTube和LiveJournal数据集来自斯坦福大学大型网络数据集收集(http://snap.stanford.edu/)。WordNet代表英语单词之间的关系,和标签的节点代表不同的词类。DBLP提供了一个全面的计算机科学的研究论文列表。我们选择了作者信息、字段和期刊建立图表。DBpedia爬从维基百科。我们集群DBpedia数据图包括人数据集和其链接,如(36]。提取YouTube视频共享网站YouTube。上传工具,我们选择了视频id和类别构建图表。LiveJournal上是一个免费的在线博客社区,用户声明彼此友谊,用户日志,个人博客,共享博客。的细节上面的数据表2。DBpedia和LiveJournal上没有标签;在[36),我们已经进行了分配一个标签为每个顶点从合成标签组大小50和100,分别。

我们使用R-MAT图生成器生成四种合成数据集(42)与G₁,G₂,G₃,G₄,10⁴,10⁵,10⁶,10⁷分别是顶点的数量。每个合成图的边数是10 |V|。标签的节点是随机从∼E,和边的权值是随机生成的从[0,1],在[引用13]。

5.1.2中。查询集

我们确保每个查询都有至少一个匹配的数据图。我们通过深度优先搜索遍历数据图(DFS)生成与查询图的大小从2到50个节点类似于现有的工作(15,24,38,39]。然后,我们随机分配标签和添加查询约束。除非显式地指定,我们感兴趣的是计算十大有趣的子图(K= 10)。

5.2。实验分析

5.2.1。预处理时间和内存的成本

预处理子图查询至关重要,因为它可以极大地减少内存消耗,以及总运行时。数据(11日)和11 (b)显示预处理时间的比较不同大小的数据集和合成数据集。

必要的预处理塞西的任务包括查询找到根节点,生成查询树,确定匹配订单,打破自同构,找到集群轴心。因为预处理主要是针对查询图,我们选择妥协查询图25节点的大小。塞西需要处理时间小于执行数据图由于规模较小。

PBSM的预处理包括数据图压缩,在这两个顶点是等价的。它遍历数据图找到等价的顶点和合并来减少数据图的大小。因为它不涉及大量的计算,它有最短的预处理时间与其他方法相比。

该方法在39)包括DVI索引的创建,其中包括目的地顶点数(")和边排序列表。获取所有的陷落,它使用广度优先搜索(BFS)从一个顶点到另一个距离D。在补充陷落,它使排序列表。DVI的预处理时间的影响D。

方法的预处理时间提出了包括数据图压缩,STFIndex创建和STFIndex分区。因此,与PBSM和DVI相比,它需要更多的预处理时间。自去年三种方法的预处理操作是独立的查询图,只预处理数据图。因此,可以离线完成的操作而不影响在线查询的效率。

图12显示内存的比较成本STIndex, PBSM, DVI,塞西在不同的数据集。摘要STIndex将取代原始数据的存储图,和内存成本只有STIndex没有额外的存储。PBSM的内存成本包括数据图和压缩的信息图。的内存成本压缩比的影响。DVI的信息包括数据图和DVI指数,膨胀的顶点数和边排序列表。根据的增加D,更多的邻居需要存储的信息,和DVI的内存成本将增加成倍的增加D。塞西需要存储数据图,图预处理的信息查询以及查询图的候选人。我们选择5节点的查询图实验。它仍然需要更多的内存空间。

5.2.2。并行处理效率

在本节中,我们评估的效率STFIndex分区。我们比较的并行处理和单独的机器解决方案越来越多的查询图大小两个真实数据集DBLP和LiveJournal,和一个合成数据集G₃。

如图13,横坐标是查询图中的节点数量,纵坐标是加速度比值分区和单机查询后的查询效率。我们可以看到较大的数据图和数据图标签越多,越明显加速。

加速的主要原因是,单机处理解决方案需要验证一个接一个完成指数根据匹配原则获得候选节点和边集。然而,当分区索引,我们可以从不同的分区搜索候选节点和边平行。由于分区方法本文根据节点类型、分区相关的边缘信息可以同时复制到分区。这可以有效地减少不同分区之间的通信开销,和并行效率相对较高。加速的趋势略比公寓有时。这是因为,增加查询的图表,并行处理需要更多的时间来加入subresults获得最终的子图。

5.2.3。个性化Top-K有趣的子图查询的运行时间

我们已经运行实验,发现十大(K= 10)子图查询的图表没有重量(问)如图1 (b)和体重(查询图问′)如图7在五个不同的真实数据集和大型合成数据集G₄。图14显示运行时间的加速比该方法和IEM PBSM,塞西。

如图14,STF_ISQtop-k优于IEM平均1.75和5.02问和问分别′。加速的主要原因是,IEM利用DVI指数过滤候选人一个接一个,不考虑同形像的潜在价值节点。的加速问′大于问。这是因为IEM需要搜索所有数据图同构子图,选择排名前十的排名结果,这需要更多的时间。然而,STF_ISQtop-k修剪边缘的重量不符合约束在过滤阶段,避免重复计算。它更适合加权图查询。PBSM和STF_ISQtop-k考虑同形像的问题节点和介绍图像压缩,从而减少数据图的大小和筛选有效无效的候选人。然而,基于分区STFIndex STF_ISQtop-k实现并行计算的阶段过滤器,而不是像PBSM遍历整个超图。

此外,由于PBSM需要滤子图查询现有的重量不符合约束的所有查询结果,过滤重复。因此,STF_ISQtop-k比PBSM都好问和问′,特别是在加权查询图问′。塞西的运行时间包括预处理,塞西创建和枚举的子图。尽管塞西的预处理在线执行,并行技术加速查询。

5.2.4。查询图的规模和影响K

我们评价查询图的影响大小在有趣的子图查询的运行时间。我们限制与两个真实数据集WordNet和YouTube和分配权重随机查询的图表。每个方法的运行时间增加而增长的查询图的大小。

如图15,STF_ISQtop-k IEM最明显的优势,尤其是在大型图。这是因为IEM需要再次验证结果集和筛选的子图边满足查询条件。与此同时,随着查询图的大小增加,迭代的数量增加,从而导致更大的查询时间显著增加。与IEM相比,PBSM利用压缩技术有更好的查询性能。它还缺乏最优加权查询查询战略图,只过滤结果再次得到令人满意的最终的子图。塞西采用并行处理技术能够有效地提高查询的时间,但它需要为每个查询创建一个塞西指数图。然而,本文的方法只有创建索引的离线数据图,可多次施工完成后。塞西不考虑同型node-compression,这就需要为每个查询过滤节点提取候选节点。的加速STF_ISQtop-k来自减少冗余过滤,这李子不满足子图。的查询图的大小越大,更多的节点和边被压缩,STF_ISQtop-k的优势更明显。

图16显示变化的影响K为我们STF_ISQtop-k,验证DBLP真实数据集。从图可以看出,查询时间查询图大小的增加而增加,但相对逐渐增加。当查询图问是固定的,K更改,查询时的波动很小。因此,验证,STF_ISQtop-k具有良好的可伸缩性。

6。结论

在本文中,我们提出一种新颖的智能解决方案Top-K有趣的子图查询。具体地说,拟议中的ISGC策略可以压缩数据图更小的尺寸和过滤多个批处理无效的节点和边。拟议的辅助数据结构STFIndex代表所有拓扑信息压缩图,可以代替原始数据图的存储。与此同时,将创建STFIndex离线提高在线查询的效率。我们也提出一个基于ELSV分区方法将STFIndex划分为多个分区,每个分区中实现并行查询。STFIndex的帮助下,我们提供一个个性化的Top-K有趣的子图查询方法在大型标签图STF_ISQtop-k命名。它包含MDF策略,UBV (Size-c)匹配,和橙汁方法,用于过滤掉尽可能多的虚假的候选人来实现快速连接的子查询的结果。实验结果表明,该方法可以执行Top-K有趣的大标签图子图查询效率,和查询结果在实际应用有实际意义。在未来,我们将在其他领域的应用我们的解决方案来解决问题,提高我们的Top-K有趣的子图查询的方法。

数据可用性

使用的数据来支持本研究的发现是可用的http://snap.stanford.edu/。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作是由中国国家重点研究和发展计划(批准号2019 yfc0850103),中国国家自然科学基金(批准号。61472169,61502215,62072220,和U1811261),中国博士后科学基金资助项目(批准号2020 m672134),辽宁省教育部门的科学研究基金(批准号LJC201913),辽宁公众舆论和网络安全大数据系统工程实验室(批准号04-2016-0089013)。

引用

1. a . b .桑麦资和t可以比较的组织/疾病特定集成网络使用定向graphlet签名,“BMC生物信息学,18卷,不。4,每周,2017页。视图:出版商的网站|谷歌学术搜索
2. l . Bingxian z志诚,w . Lei et al .,“围wi - fi报道:一个众包的方法利用物理层信息,”《第13届IEEE国际会议传感、通信、和网络(SECON),页1 - 9,伦敦,英国,2016年6月。视图:谷歌学术搜索
3. j·l . b . Lu Wang刘et al .,“拉萨:位置感知无线物联网系统的安全访问控制,”移动网络和应用程序,24卷,不。3、748 - 760年,2019页。视图:出版商的网站|谷歌学术搜索
4. x j·李·g·h·杨,“图基于理论将随机复杂动力网络的同步,”IEEE神经网络和学习系统,28卷,不。2、1 - 11,2017页。视图:出版商的网站|谷歌学术搜索
5. 腾讯科技:“微信的月度活跃用户11.2亿,year-one-year增加了6.9%,”2020年,https://tech.qq.com/a/20190515/007600.htm。视图:谷歌学术搜索
6. 腾讯科技,“Facebook的月度活跃用户24.5亿,收入在第三季度year-one-year增加了30%,”2020年,https://tech.qq.com/a/20191031/001015.htm。视图:谷歌学术搜索
7. e . Abdelhamid作为礼尚往来,z Khayyat, p . Kalnis”旋转子图同构:乐观,悲观主义者和现实主义者,”《22日国际会议上扩展数据库技术,发债公司2019《里斯本条约》,页361 - 372年,葡萄牙,2019年3月。视图:谷歌学术搜索
8. x,徐,l·l·柴y . j .杨和y . p .茶,“大规模高效的分布式查询处理RDF图数据,”软件学报,30卷,不。3、498 - 514年,2019页。视图:出版商的网站|谷歌学术搜索
9. 吴b和h沈”,利用大数据高效密集的子图发现方法,”IEEE大数据,3卷,不。3、334 - 348年,2017页。视图:出版商的网站|谷歌学术搜索
10. m . Abulaish z . a·安萨里和s . Jahiruddin”SubISO:一个可伸缩的和新颖的方法搜索子图同构的大型图表,”学报》第11届国际会议上通信系统和网络(COMSNETS),页1 - 8,班加罗尔,印度,2019年1月。视图:谷歌学术搜索
11. l .赖z, z杨et al .,“及时的数据流分布的子图匹配,”美国养老,12卷,不。10日,1099 - 1112年,2019页。视图:出版商的网站|谷歌学术搜索
12. h . j . Kim Shin W.-S。汉族,香港,和h . Chafi“驯服为RDF查询处理,子图同构”美国养老科哈拉海岸,页1238 - 1249年,美国,2015年2月,你好。视图:谷歌学术搜索
13. m·古普塔j .高,x, h .凸轮和j·汉,“Top-K有趣的子图发现信息网络,”《IEEE 30日国际会议数据工程,ICDE,第831 - 820页,芝加哥,2014年3月,美国。视图:出版商的网站|谷歌学术搜索
14. x x, c .贾l .叮叮,和b的歌,“动态top-K有趣的子图查询在大规模标注图,“信息,10卷,不。2、61 - 83年,2019页。视图:出版商的网站|谷歌学术搜索
15. j·r·乌尔曼,”子图同构算法”,ACM的杂志,23卷,不。1,31-42,1976页。视图:出版商的网站|谷歌学术搜索
16. m . r . Garey d·s·约翰逊,电脑和棘手:np完全的理论指南w·h·弗里曼,纽约,纽约,美国,1979年。
17. l . p . Cordella·福贾c桑松,和m . Vento”(子)图同构算法匹配的大型图表,“IEEE模式分析与机器智能,26卷,不。10日,1367 - 1372年,2004页。视图:出版商的网站|谷歌学术搜索
18. l . b .持有人、d·库克和s . Djoko“子结构发现抑制系统,”《车间在数据库知识发现,KDD ' 94,第180 - 169页,西雅图,佤邦,美国,1994年7月。视图:谷歌学术搜索
19. f .朱问:瞿,d . Lo x, j .汉和p . s . Yu”矿业top-K大型结构模式在一个巨大的网络,”学报》第37届国际会议上非常大的数据基地,VLDB”11,第818 - 807页,西雅图,佤邦,美国,2011年8月。视图:谷歌学术搜索
20. 答:射线、l . b .持有人和a . Bifet”有效的频繁子图挖掘大型流图”,智能数据分析,23卷,不。1,第132 - 103页,2019。视图:出版商的网站|谷歌学术搜索
21. h·a·k·辛格和他“查询语言和图形数据库访问方法,”学报2008年ACM SIGMOD国际会议管理的数据,SIGMOD 2008加拿大温哥华,页405 - 418,2008年6月。视图:出版商的网站|谷歌学术搜索
22. p .赵和j·汉”,在大型网络图查询优化,“美国养老,3卷,不。1 - 2、340 - 351年,2010页。视图:出版商的网站|谷歌学术搜索
23. f . Bi l . Chang x林et al .,“有效的子图匹配通过推迟笛卡尔产品,”《2016国际会议管理的数据,SIGMOD 16,页1199 - 1214年,旧金山,美国,2016年6月。视图:出版商的网站|谷歌学术搜索
24. b·巴特·h·刘,h·豪伊黄”塞西(CECI):紧凑嵌入集群指数可伸缩的子图匹配”《2019国际会议管理的数据,SIGMOD 19,页1447 - 1462年,荷兰阿姆斯特丹,2019年6月。视图:出版商的网站|谷歌学术搜索
25. h·a·k·辛格和他“过滤策略不精确的子图匹配的多路网络”学报2019年IEEE国际会议上大数据洛杉矶,页4906 - 4912,美国2019年12月。视图:出版商的网站|谷歌学术搜索
26. g·m·汉h . Kim顾et al .,“有效的子图匹配:协调动态编程、自适应匹配订单,和失败联系在一起,”学报2019年ACM SIGMOD国际会议管理的数据,SIGMOD 19,页1429 - 1446年,荷兰阿姆斯特丹,2019年6月。视图:出版商的网站|谷歌学术搜索
27. y公园,s . Ko, s . s . Bhowmick et al .,“G-CARE:基数估计方法的性能基准测试框架子图匹配”学报2020年ACM SIGMOD国际会议管理的数据,SIGMOD 20波特兰,页1099 - 1114,或者美国,2020年6月。视图:出版商的网站|谷歌学术搜索
28. N.-T。勒,签证官,l . b .问:阮h . Fujita和b·勒”挖掘加权子图在一个大型图表,“信息科学卷,514年,第165 - 149页,2020年。视图:出版商的网站|谷歌学术搜索
29. w·s·汉、j·李和j·h·李,“TurboISO:超速和健壮的子图同构在大型图像数据库搜索,”学报2013年ACM SIGMOD国际会议管理的数据,SIGMOD 13,页337 - 348,纽约,纽约,美国,2013年6月。视图:谷歌学术搜索
30. 任x和j·王”,利用顶点在大型图形加速子图同构的关系,“美国养老,8卷,不。5,617 - 628年,2015页。视图:出版商的网站|谷歌学术搜索
31. 段h·张,谢x, y, y,“子图匹配的算法基于自适应结构标记为有向图数据的总结,“中国电脑杂志,40卷,不。1、52 - 71年,2017页。视图:出版商的网站|谷歌学术搜索
32. c . Nabti h·西巴,“大规模图数据的查询:压缩和搜索方法,”未来一代计算机系统卷,74年,第75 - 63页,2017年。视图:出版商的网站|谷歌学术搜索
33. x、b, f·朱,j .汉“Top-K聚合查询在大型网络,”学报》第26届国际会议上数据工程,ICDE 2010长滩,页377 - 380年,CA,美国,2010年3月。视图:出版商的网站|谷歌学术搜索
34. 杨,汉族,严x, y . Wu”快top-K搜索知识图”学报2016年IEEE第32国际会议数据工程,ICDE 162016年5月,芬兰赫尔辛基。视图:出版商的网站|谷歌学术搜索
35. x z太阳、h·霍和陈,“快top-K图相似性搜索矩阵,通过代表”IEEE访问,卷99,p . 2018。视图:出版商的网站|谷歌学术搜索
36. z, a·w·傅,r·刘”多元化top-K子图查询在一个大型图表,”学报2016年ACM SIGMOD国际会议管理的数据,SIGMOD 16,页1167 - 1182年,旧金山,美国,2016年6月。视图:出版商的网站|谷歌学术搜索
37. j . p . Fournier-Viger c . Cheng C.-W。林,云,r . Kiran,“TKG:高效的top-K频繁子图挖掘”学报》第七届国际会议上大数据分析,汇业银行2019,页209 - 226,艾哈迈达巴德,印度,2019年12月。视图:出版商的网站|谷歌学术搜索
38. w·陈,j . Liu x, z . Chen和k·李,“PBSM:一个高效top-K子图匹配算法”,模式识别与人工智能》国际期刊上,32卷,不。6、2018。视图:出版商的网站|谷歌学术搜索
39. n .阿明k .汗,b . Dolgorsuren和y . k . Lee”与加权查询语义提取top-K有趣的子图,”《IEEE国际会议上大数据和智能计算、BigComp,页366 - 373,济州岛,韩国,2017年2月。视图:出版商的网站|谷歌学术搜索
40. a . Bendimerad a·梅尔·j . Lijffijt m . Plantevit c . Robardet和t . d .、“矿业主观有趣的子图,”学报》第14届国际研讨会在采矿和学习图表(MLG),伦敦,英国,2018年5月。视图:谷歌学术搜索
41. n . Jayalakshmi p Padmaja, g . j . Suma“有趣的方法从web日志数据使用W-Gaston子图挖掘算法,”国际期刊的不确定性、模糊性和以知识为基础的系统,27卷,不。2、277 - 301年,2019页。视图:出版商的网站|谷歌学术搜索
42. d . Chakrabarti y詹和c·凯利,“R-MAT:递归图挖掘模型”《暹罗国际会议数据挖掘、长效磺胺的04,页442 - 446,,布纳维斯塔湖FL,美国,2004年4月。视图:出版商的网站|谷歌学术搜索

版权

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