melody marks 肛交 基于SQL的图一样性查询轨范

跟着互联网、物联网和出动互联等信息工夫的发展， 图结构数据在现时社会越来越普及， 在酬酢集聚、常识图谱、语义网、生物信息学和化学信息学等领域齐有粗造的应用[1-3].跟着图结构在复杂数据建模方面的粗造应用， 图数据顾问工夫合手续得到了粗造存眷， 而其中， 怎样从图数据集结中快速检索数据， 如故成为一个研究热门[4].在图查询中， 一样性查询是一种罕见紧要的查询式样.一样性查询是指给定一个查询图和阈值T， 复返图数据集结中与查询距离不大于T的统统图数据.处理一样性查询时melody marks 肛交， 需要进行图一样度策画.研究学者如故提议了许多种图一样性度量轨范， 其中最渊博适用的即是图剪辑距离[5， 6].但是图剪辑距离的策画如故被解释是NP防碍[7].为了快速有用地复返图查询的闭幕， 面前主要选用“过滤+考证”的两阶段处理机制.在这种机制中:

●当先预界说过滤端正， 即， 用复杂度较低的轨范快速策画出图数据集结中每个图与查询图的剪辑距离的范围(用上界和下界暗意)， 其中， 剪辑距离的上界(下界)神情了两个图距离可能的最大值(最小值);

●其次， 利用下界和上界将集结中不可能出当今闭幕集(其与查询图的剪辑距离的下界 > T)或者详情出当今闭幕集的图(其与查询图的剪辑距离的上界 < T)先进行过滤， 从而生成范围较小的候选集;

●终末对候选集进行图剪辑距离策画， 得到最终的闭幕集.

现存一样性查询的图过滤轨范中具有代表性的有4种:基于label的图一样查询轨范[8]、基于path的图一样查询轨范[9]、基于star的图一样查询轨范[10]和基于tree的图一样查询轨范[11].这些轨范选用图中的子结构一样性推测图剪辑距离， 通过策画时分复杂度较低的近似距离提高过滤阶段的效率.然则本文通过实考解释:这些近似策画轨范通常具有自身的优污点和适用性， 莫得一种算法不错在统统应用场景下产生的图数据集结中齐具有优厚性.为了贬责已有轨范渊博存在的问题， 本文提议一种全新的过滤战略， 使得多样剪辑距离的近似策画轨范不错互相间舍短取长， 造成更为精准、健壮和实用的图剪辑距离的近似度策画轨范.

接头到已有的经典过滤轨范， 如基于图的不同子结构信息label， path和tree等， 很难径直想象一种结伙的索引结构来撑合手已有轨范.为了充分诱骗已有过滤端正来提高过滤效率， 本文提议了面向关系型数据库的结伙过滤框架.该框架既不错撑合手已有过滤端正的松耦合诱骗， 又不错利用关系型数据库自己的健壮性和实用性[12]来提高算法的适用性.其主要念念想是:

●当先， 基于PostgreSQL竣事将图数据库转化为关系型数据库进行存储;

●然后， 在PostgreSQL中使用PL/SQL竣事基于label， star， path和tree这4种模子的剪辑距离近似策画的算法.

为了削弱一样性查有计划题中候选图的范围， 本文提议了一种松耦合的过滤轨范， 对已有的4种近似距离策画轨范进行有用的诱骗， 从而得到更紧的下界和上界， 在过滤阶段剔除更多的非闭幕图， 极地面减少图剪辑距离的策画， 提高图一样查询的效率.当先， 将查询图的范围信息和节点标签信息与图数据库中的图进行比拟， 利用基于label的图过滤端正先将高偏差的图剔除.其次， 策画复杂性相对较高的基于path， tree或者star的近似距离， 中式其中最大的下界值和最小的上界值来得回更紧更精准的近似距离， 从而得到一个较小的候选集.终末， 通过策画候选蚁集的图剪辑距离， 复返称心查询要求的图集结.

本文主要孝顺为:

●提议了一种全新的面向关系型数据库的图过滤战略， 既不错为已有的过滤轨范提供结伙的过滤框架， 又不错充分利用已有过滤端正的松耦合诱骗轨范得回愈加高效的坎坷界， 减少候选蚁集图的数量， 从而减少骨子剪辑距离的策画， 提高一样性查询的效率;

●面向关系型数据库的过滤框架， 完全基于SQL的竣事轨范， 无需修改关统统据库的内核.况兼， 不错充分利用关系型数据库的健壮性和实用性， 提高图一样查询算法在不同领域问题的适用性;

●有计划执行闭幕解释， 本文提议的面向关系型数据库的图过滤战略优于已有的图一样查询算法.

本文第1节对已有的图一样查询轨范有计划责任进行分类追究.第2节给出主要问题界说.第3节针对本文提议的问题， 给出基于已有责任的贬责决策， 追究分析出这些轨范的劣势， 并提议一种愈加有用的面向关系型数据库的轨范.第4节通过一系列执行对本文提议的轨范与已有责任进行比拟， 分析本文轨范的有用性.终末追究全文， 并提议翌日值得存眷的研究主义.

1 有计划责任 1.1 图一样度策画

图一样查询是一种紧要的查询式样， 应用粗造.一样性查询是指复返数据库中与查询图一样的图集结.处理一样性查询时， 当先需要进行图一样度策画.早期的研究学者主要提议了启发式的图一样性度量轨范[8， 13-15].文件[13]提议了一种基于节点各异的图一样度量圭臬.文件[15]基于random walk界说了图之间的一样性.文件[8， 15]则在文件[13]的基础上进一步利用节点的承接节点信息来推测图的一样性.其后的研究学者启动提议基于最大行家子图的一样性度量轨范[16]和基于剪辑距离的图一样性度量轨范[5].文件[20]利用雷同的念念想， 使用SQL回应度量空间下的一样度查询， 但该责任与本文的研究问题不同.在已有的轨范中， 最渊博适用的即是图剪辑距离.因此， 本文华用剪辑距离来贬责图一样性查询处理问题.

文件[5]完好综述了图剪辑距离的策画轨范[5]， 该文把已有策画轨范分为两大类:精准策画轨范和近似策画轨范.精准策画最常用的轨范是A*算法[17].然则， 由于剪辑距离的策画是NP防碍[7]， 这类精准的算法通常因复杂渡过高而不具有实用性.为了幸免这个问题， 一些复杂度较低的近似剪辑距离的策画轨范被提议， 用于过滤偏差较大的图[7， 9-11， 18].

1.2 图一样查询轨范

由于图剪辑距离的策画过于复杂， 因此很难找到一种高效的策画轨范.已有轨范选用“过滤+考证”的框架机制来加快图一样查询的速率， 其主要念念路是:通过一些复杂度较低的近似距离先过滤掉造作闭幕， 然后再通过骨子剪辑距离的策画对剩下的候选数据进行考证.面前， 基于剪辑距离的图一样查询算法把柄其所选用的不同过滤式样， 主要分为3大类:基于label的图一样查询轨范、基于path的图一样查询轨范和基于tree的图一样查询轨范.

●基于label的图一样查询轨范

早期的轨范念念路比拟直不雅， 即是利用图的节点和边的数量各异当作过滤条目[13]， 即， 两个图之间节点的数量各异与边的数量各异之和是两个图之间剪辑距离的一个下界.文件[8]在文件[13]的基础上进一步接头节点和边的label各异， 即:先永别将节点和边的label进行分类， 两个图之间每一类label的数量各异之和当作剪辑距离的一个下界.由于背面提议的下界比前边的相对较紧， 因此本文结伙将这类轨范称为基于label的图一样查询轨范.然则， 这类轨范忽略了图的结构信息， 下界通常很松， 因此过滤后果有限.

●基于path的图一样查询轨范

这类轨范的基本念念想来源于字符串的q-gram数量过滤端正， 是一种基于图结构的过滤轨范.这类轨范中最具代表性的是文件[9].这类轨范把图中的子结构path当作q-gram， 然后利用字符串q-gram数量策画剪辑距离的下界.这里的path常常界说为图中的一个节点和边序列， 其中， 大肆两个相邻节点之间均有一条边， 而边的总和即对应q-gram的q值.把柄这个界说， 给定两个图， 这类轨范当先需要索求两个图的统统path， 组成两个path集结; 然后， 通过策画集结的错杂得到两个图的共同path数量， 只消这个数量查过一定的阈值， 两个图的距离才会小于某个阈值.文件[18]指出:由于一个度数较大的节点剪辑操作将引起多数的path产生各异， 因此， 基于q-gram共同数量的下界可能会很松， 从而导致过滤后果有限.

●基于tree的图一样查询轨范

基于tree的这类轨范亦然一种基于图结构的过滤轨范， 然则由于过滤端正策画轨范的不同， 不错进一步分为两种轨范， 即， 基于q-gram数量的过滤轨范[11]和基于二分匹配[19]的过滤轨范[7， 10， 18].其中， k-at算法提议将图中的子结构k承接树当作q-gram， 然后利用两个图之间共同的q-gram数量策画剪辑距离的下界[11].文件[7， 10]提议了基于图中的子结构star的过滤轨范， 这里的star不错看作念k=1的k承接树.然则， 这些轨范并莫得选用很松的q-gram数量当作过滤条目， 而是提议一种基于二分匹配的下界策画轨范.文件[18]亦然基于二分匹配策画剪辑距离的下界， 不同的是， 其选用的过滤子结构是branch， 即， 去掉统统子节点只包含根节点和承接边的star.这类基于tree结构的轨范所提议的剪辑距离的下界的过滤后果也直接管到图的节点度数影响， 因此只适用于平均节点度数较低的图数据库.

要而论之， 现存的轨范提议的过滤端正均具有自身的优污点和适用性， 很难有一种算法不错适用于多样图数据库或者优于统统其他算法.

2 筹画常识 2.1 问题界说

本文主要研究无向浅易图的一样查有计划题.无向浅易图指无向带标签的无环连通图， 不错通过四元组g=(V， E， lv， le)暗意， 其中， V代表g图中统统节点的集结， E代表统统边的集结， lv代表节点标签的集结， le代表边的标签的对应集结.本文的其他标注见表 1.

Table 1 Paper notations 表 1 文中标注

界说1(图剪辑距离).给定两个图r和图s， 两图之间的剪辑距离ged(r， s)即为将图r改造成图s所需的最小剪辑操作数量.图的剪辑操作东要包括以下6种.

●在图中插入一个孤苦孤身一人的节点;

●从图中删除一个孤苦孤身一人的节点;

●在图中修改一个节点的标签;

●在图中插入一条连续两个节点的边;

●从图中删除一条边;melody marks 肛交

●在图中修改一条边的标签.

界说2(基于剪辑距离的图一样查有计划题).给定一个图的集结D={g1， g2， …， g|D|}， 待查询的图q， 阈值T， 找到统统图gi与待查询图q的剪辑距离称心不等式ged(gi， q)≤T的图的集结.

图 1给出了3个化学结构， 轮番为甲烷(g1)、乙烷(g2)、乙烯(g3)， 光显均是无向浅易图.

Fig. 1 Example of three data graphs g1， g2 and g3 图 1 图集结示例

给定图的集结包含图g1， g2和g3， 咱们指定待查询图为q=g1， 其中， 不错策画得到ged(g1， q)=0， ged(g2， q)=7， ged(g3， q)=6.淌若剪辑距离的阈值是T=6， 那么由于ged(g1， q)≤T和ged(g3， q)≤T， g1和g3将出当今闭幕集里， 而g2将不在闭幕集里.

2.2 现存代表性算法

如界说2所示:要贬责该问题， 一般需要遍历数据集D中统统的图， 策画每一个图与待查询图的剪辑距离， 然后再把柄给定的阈值筛选出一样图.然则， 图剪辑距离的策画已被解释是NP防碍[7]， 策画的复杂度罕见大， 面前尚未有任何轨范能快速策画出图的剪辑距离.因此， 对数据集内一谈的图进行遍历策画光显不切骨子.为了提高图一样查询的速率， 现存的轨范通常选用“过滤+考证”的两阶段处理机制.现存的图过滤轨范中， 最具代表性的有4种:基于label的过滤轨范、基于star的过滤轨范、基于path的过滤轨范和基于tree的过滤轨范.以下具体先容这4种经典的图一样查询算法.

2.2.1 基于label的过滤轨范

通过两个图的标签来度量一样性是最为基础的一种过滤轨范[8].把柄图剪辑操作的界说， 咱们不错以为:淌若两个图具有不同个数的边和节点， 则光显需要通过一定的剪辑操作才能使得图同构.因此， 不错得到公式(1):

$ ged\left( {r， s} \right) \ge abs(V\left( r \right)|-\left| {V\left( s \right)} \right|) + abs(E\left( r \right)|-\left| {E\left( s \right)} \right|) $ (1)

图r与图s的剪辑距离一定小于或等于两个图的节点个数之差加上边条数之差.因此， 浅易的基于label的过滤端正界说为:找到集结D中的统统称心不等式abs(V(r)|-|V(s)|)+abs(E(r)|-|E(s)|)≤T的图.

再进一步接头， 由于节点和边的标签不同， 可能也会产生相应的剪辑操作.因此， 咱们对公式(1)不错进行相应的优化， 即:先通过标签进行分类， 然后再对每一类进行策画.见公式(2):

$ ged(r， s) \ge \sum {abs(|V{{(r)}_l}|-|V{{(s)}_l}|) + abs(|E{{(r)}_l}|-|E{{(s)}_l}|)}， l \in {l_v}， {l_e} $ (2) 2.2.2 基于star的过滤轨范

把柄图的结构进行子图明白亦然一种近似策绘图剪辑距离的念念路.当先， 咱们将图拆解为多个星形结构[7].星型结构即为由一个中心节点以及与它有边相连的节点所组成的深度为1的树结构.星型结构不错用三元组s=(r， L， l)暗意， 其中， r暗意根节点， 即中心点， L代表统统的叶子节点集结， l为叶子节点对应的标签集结.是以， 关于有n个节点的图g， 就会得到n个对应的星型结构， 星型结构的集结用S(g)暗意.图的剪辑距离策画也就转化为对星型结构进行剪辑距离策画.

咱们给出星型结构的剪辑距离(star editdistance， 简称SED)策画公式， 见公式(3):

$ \begin{array}{l} sed\left( {{s_1}， {s_2}} \right) = T\left( {{r_1}， {r_2}} \right) + d\left( {{L_1}， {L_2}} \right) = T\left( {{r_1}， {r_2}} \right) + \\ abs\left( {\left| {{L_1}} \right| + \left| {{L_2}} \right|} \right) + \max \left( {\left| {{L_1}} \right|， \left| {{L_2}} \right|} \right)-\left| {\left| {{L_1}} \right| \cap \left| {{L_2}} \right|} \right| \end{array} $ (3)

淌若s1与s2的根节点具有相通的标签， 则T(r1， r2)的值为0;不然为1.将其与图剪辑距离的改造见公式(4)、公式(5):

$ md(r， s) = \mathop {{\rm{min}}}\limits_P \sum\limits_{{s_i} \in S(r)} {sed({s_i}， P({s_i}))} $ (4) $ \frac{{md(q， g)}}{{({\rm{max}}\{ 4， [{\rm{max}}\{ \delta (q)， \delta (g)\} + 1]\} )}} \le T $ (5)

图剪辑距离的策画其实转化为了对图r和图s的星型结构集结找到最优匹配， 要找到剪辑距离的下界， 使得终末匹配得到的SED之和最小， 咱们用mapping distance(MD)来代表这个最优解.因此， 最优匹配的求解念念路为:当先， 将图r和图s的星型结构两两策画SED， 从而组成一个权重矩阵， 淌若两个图所具有的星型结构个数不同， 则通过插入空节点的轨范组成矩阵[10].之后， 将所得到的矩阵当作输入参数， 选用匈牙利算法[19]找到最优匹配.

因此， 基于star的过滤端正界说为:给定阈值T， 过滤得到集结D中的图g与q称心不等式(5)的图集结.

2.2.3 基于tree的过滤轨范

基于tree的过滤端正[11]主要通过图中的子树进行构建.通过深度优先搜索， 指定一个启动节点， 不错将与其相邻的节点当作叶子节点， 通过递归的式样构建无穷深度的树， 咱们把这个树称为承接树(adjacent tree， 简称AT).因为承接树结构的复杂性， 在策画中会带来不消要的效率问题， 是以咱们截至了承接树的深度k， 将指定深度的承接树(k-AT)当作基于tree的过滤端正中枢.

因此， 过滤端正的不等式见公式(6):

$ \left| {k-ATs\left( r \right) \cap k-ATs\left( s \right)} \right| \ge \left| {V\left( r \right)} \right|-T \cdot 2{(\delta \left( r \right) - 1)^k}^{ - 1} $ (6)

将图r和图s转化为从图中每个节点登程的k-AT的集结.不等式的左半边即为两个集结所具有相通结构k-AT的个数.

2.2.4 基于path的过滤轨范

基于path的过滤端正[9]亦然一种基于图结构的过滤轨范.当先， 需要找到图中指定长度q的统统旅途.本文中选用深度优先搜索算法进行path索求.因为旅途有启动节点和闭幕节点， 永别从启动节点和闭幕节点登程， 将会得到两条序列， 对这两条序列咱们保留字典序较小的一条.将图g中每个节点登程的旅途组成的集结用P(g)暗意， 则通过过滤的图需要称心公式(7)， 不等式左半边为图r和s的旅途集结， 右半边为取到两个图中度数减去阈值乘以最大度的较大值.

$ \left| {P\left( r \right) \cap P\left( s \right)} \right| \ge \max \left( {\left| {P\left( r \right)} \right|-T \cdot \delta \left( r \right)， \left| {P\left( s \right)} \right|-T \cdot \delta \left( s \right)} \right) $ (7) 2.3 图一样查询框架

如图 2所示， 图的一样查询框架主要分为特征索求、过滤和考证这3个部分.当先， 把柄对应的过滤算法的所需参数， 对待查询的数据集D进行特征抽取， 如对图进行遍历得到旅途， 统计图中极点和边的个数等; 然后就参预过滤部分的操作， 即， 调用对应的过滤算法产生通过过滤的候选数据集， 从而将完全不一样的图丢弃; 终末， 将候选蚁集的图进行精准的图剪辑距离策画， 从而得到最终的一样查询闭幕集结.

Fig. 2 Framework of graph similarity search based on edit distance 图 2 基于剪辑距离的图一样查询框架

这种较为经典的过滤框架是一种贬责图一样查询的比拟好的轨范， 不错较地面擢升图一样查询的效率.但是当作一种执行框架， 关于骨子的图结构应用环境不成作念到很好的撑合手.如在酬酢集聚的应用中， 把柄酬酢关系所构建的图结构会不休地更新， 那么每次更新齐需要对图的特征进行再行索求， 进而通过“过滤+考证”来进行图一样查询， 这种串行的处理现象会使得骨子应用场景下， 该框架的效用较低.同期， 针对现时大数据环境下的图结构所具有的数据量庞杂的脾性， 框架莫得给出一种很好的存储贬责决策来保证对图数据的有用顾问.因此， 对现存的图一样框架进行优化是罕见有必要的.

通过分析图中基于剪辑距离的图一样查询过程， 咱们识别出影响搜索性能最紧要的影响身分(如图 2的过滤端正部分所示)， 即， 图过滤端正的想象(见第3节).本文在现存的图过滤轨范中中式最经典的4种(见第2.2节)， 并逐一竣事其图一样查询算法.咱们从PubChem数据蚁集抽样得到执行数据集， 将竣事的4种算法在抽样的图集上进行执行(执行闭幕见第4.1节)， 追究分析执行解荒疏现:已有的端正自己具有优污点和适用性， 这4种轨范莫得一种或者统统地优于其他的轨范.为了最猛进度地保留已有轨范的优点， 幸免污点， 本文提议了一种全新的面向关系型数据库的过滤框架， 新的过滤框架不错将这4种图的剪辑距离的近似策画轨范进行有用诱骗， 求得更紧的坎坷界， 造成了或者进行罕见高效地进行剪枝的轨范.

3 面向关系型数据库的图一样查询算法

本节要点答复面向关系型数据库的图一样查询算法， 当先， 简要先容所提议的全新过滤框架以及新的过滤端正.然后， 将其在PostgreSQL这一开源的关系型数据库中的竣事念念路进行神情.终末， 概述先容面向关系型数据库的图一样查询框架， 况兼提议了基于图一样框架的图数据顾问轨范.

3.1 图结构在关系型数据库中的关系现象

当作一种最为渊博的结构化数据存储用具， 关系型数据库与结构化查询话语(SQL)的诱骗一直在数据操作方面发扬讲求.但是现时， 跟着图结构的不绝发展， 在关系型数据库中对图结构的操作仍然撑合手不够.因此， 本文竣事一种基于SQL的图一样性过滤轨范， 充分利用关系型数据库的脾性， 增强了关系型数据库对图一样性搜索的撑合手.

咱们将统统的图存储在关统统据库顾问系统PostgreSQL中， 存储图的Graph表具有以下3个基本字段:编号(rid:integer)、节点(vertex:integer[])、边(edge:integer[])， 每一个图在关统统据库中存储为一札记载， 假定某札记载存储了图gp， 则该记载不错暗意为$(p， \{ {V_1}， {l_1}， {V_2}， {l_2}， ...， {V_n}， {l_n}\}， \{ {E_1}， {E'_1}， {E_2}， {E'_2}， ...， {E_n}， {E'_n}\} )$.通过编号独一地象征一个图， 并将极点和边选用数组的体式存储， (vk， lk)代表一个极点， 包括了极点编号和极点标签两个属性， $({E_k}， {E'_k})$代表一条边， 用边的两个端点暗意.举例， 关于图 1中的甲烷结构， 咱们将其存储为表 2中的数据表情.

Table 2 DataSchema 表 2 图存储现象

关于过滤轨范中需要用到的图特征结构， 本文通过如下的关系现象将索求得到的特征结构进行存储， 存储图的Graph表具有以下4个基本字段:编号(rid:integer)、旅途(path:integer[])、树结构(tree:integer[])、星型结构(star:integer[]).永别对Path， Tree， Star运用一个属性存储下来， 并用rid象征这些特征所属的图.关于图 1中的甲烷结构， 对其进行特征抽取后， 指定path的长度为2， tree的深度为1， 得到的数据表情见表 3.

Table 3 Graph structure schema 表 3 图特征存储现象 3.2 面向关系型数据库的图一样过滤轨范

因为在图一样查询过程中， 过滤部分是罕见紧要的轨范， 是以本文对原有的过滤历程进行了再行想象， 提议了一种分层过滤框架， 如图 3所示.框架的全体念念想是， 但愿通过多层过滤较好地阴事时分本钱和空间本钱.因为原有的过滤轨范齐不是完全最优的， 因此， 咱们接头将他们诱骗起来进愚弄用， 即:起原用过滤粒度最粗， 但时分复杂度最低的轨范进行过滤， 得到相应的候选集后， 由下一层的过滤轨范在所得候选蚁集进行过滤， 依此类推， 通过这种层层过滤的式样， 使得每个轨范齐能清晰最佳的过滤后果.因此， 下文中结伙使用combined-filter暗意本文所使用的过滤轨范.

Fig. 3 Novel framework of graph similarity search based on RDBMS 图 3 面向关系型数据库的全新图一样过滤框架

本文通过多数的执行得出了一种较为高效的分层过滤顺序， 即:先对数据集运用基于label的过滤， 再对得到的候选集选用基于path的过滤， 然后对得到的候选集选用基于tree的过滤， 基于star结构的过滤放到终末进行.这一过滤顺序具有罕见好的过滤智力， 况兼时分复杂度较低， 历程图如图 3所示.

底下先容combined-filter在关系型数据库中的竣事念念路.咱们在PostgreSQL中使用PL/SQL竣事了基于label， star， tree， path这4种图剪辑距离过滤算法， 并通过函数调用.因为4种轨范之间是互相颓靡的， 是以这种松耦合的式样使得轨范的普适性和踏实性齐较强， 不错便捷地镶嵌到各种关系型数据库中， 而不需要修改数据库的内核.关于这4种轨范， 咱们选用结伙的过滤算法框架进行竣事， 以此保证算法的一致性， 保证分层过滤的效率.由此得到的过滤算法框架见算法1.

算法1.过滤算法框架.

1    function FILTER(q， D， T， Cand)

2      Input:q(待搜索图)， D(数据库中的图结构数据集)， T(剪辑距离阈值);

3      Onput:Cand(候选集结).

4      Cand←Ø

5      for g∈D do

6        if filter-startegy() then

7          Add(g， Cand)

8        end if

9      end for

10      return Cand

11    endfunction

3.3 基于新式过滤框架的图一样查询算法

本文提议的新式图一样查询算法历程见算法2所示.给出一个待搜索的图q， 并给出图数据集D， 剪辑距离阈值T， 在过滤阶段中， 通过label， path， tree， star的顺序进行档次过滤， 得到候选的图集结Cand.然后， 通过调用精准的图剪辑距离策画轨范， 将Cand中的图逐一考证得到最终的闭幕集结R.因为几个过滤端正间是解耦的， 是以夹杂的过滤端正不错有多种组合， 因此擢升了图一样查询的生动性.

算法2.基于新式过滤框架的图一样度搜索算法.

1  function COMBINED-GRAPH-SEARCH(q， D， T)

2    R←Ø

3    CREATE VIEW Candidate AS

4    SELECT*FROM StarFilter(q， TreeFilter(q， PathFilter(q， LabelFilter(q， D))));

5    for g in SELECT*FROM Candidate do

6      if ExactGED(g)≤T then //策画精准剪辑距离

7        Add(g， R)

8      end if

9    end for

10  end function

因此， 在调用时图一样查询轨范时， 不错通过浅易的SQL查询语句进行调用.通过对SQL函数传入3个参数:待查询图的极点数组(vertex-array)、待查询图的边数组(edge-array)、查询阈值(T)， 即可复返查询得到的图闭幕集.示例查询语句如下所示:

自拍视频 $ {\rm{SELECT}}\;Combined-Graph-Search\left( {Vertex-Array， Edge - Array， T} \right). $ 3.4 SQL-Based图特征索求

关于特征抽取操作， 咱们诱骗SQL话语的脾性和广度优先搜索的念念想， 想象了一种效率较高的图遍历算法， 见算法3.

算法3. 图的深度优先搜索算法.

1  function BREADTH-FIRST-SEARCH(edge， node)

2    //edge边集结， node极点集结

3    WITH RECURSIVE transitive-closure(a， b， distance， paths， labels) AS

3    (

4    SELECT fromnode， tonode， 1 AS distance，

5    array[fromnode] ＄melody marks 肛交