本发明涉及图的查询处理与查询优化
技术领域：
，具体涉及一种基于编码树的gpu轴心子图匹配方法。
背景技术：
：图可以表示数据对象以及对象之间的关系，在数据结构中发挥着重要的作用。图结构在各种现实场景中应用广泛，因此对图操作的性能要求也越来越高。轴心子图匹配作为一个重要的图操作，可以应用于蛋白质交互网络功能的预测，频繁子图挖掘，邻居子图挖掘等众多领域。目前可以解决轴心子图匹配问题的方法主要有基于gpu(graphicsprocessingunit，简称gpu)的子图匹配方法和基于cpu(centralprocessingunit，简称cpu)的轴心子图匹配方法。基于gpu的子图匹配方法是通过gpu加速处理子图匹配，再从匹配的子图中找到所有与轴心匹配的节点，但是这样会产生大量不必要的中间结果，浪费内存资源。基于cpu的轴心子图匹配方法是通过机器学习来预测候选节点是不是有效节点，从而分别利用乐观和悲观方法对该节点进行验证。在预测正确的情况下，可以根据相应方法快速求解，但是在预测错误的情况下，利用相反方法进行验证会浪费大量的计算资源和内存消耗，从而降低执行效率。由于基于gpu的子图匹配方法浪费了大量的内存资源，而基于cpu的轴心子图匹配方法是一种传统的基于cpu的方法，难以有效利用gpu等新硬件的大规模并行处理能力。为了利用gpu的高并行能力，本发明采用以下思路：由于过滤效果直接影响性能，因此本发明设计了一种适用于gpu的编码过滤方式，可以并行地对候选节点进行过滤。在过滤过程中考虑节点的特征越多，过滤的效果越好。然而选用过多的节点特征会增加过滤过程的计算量，影响总体执行效率。因此不同的过滤方法会在选用节点特征时进行一定的权衡。技术实现要素：针对现有技术的不足，本发明提出一种基于编码树的gpu轴心子图匹配方法，包括：步骤1：根据查询图、数据图节点的邻居节点结构将每一个节点生成一棵具有一定层数的树；步骤2：根据数据图中的标签种类生成组的标签桶组，其中n表示标签种类数；步骤3：根据生成的组的标签桶组，将步骤1生成的每个图节点的树分割为个树并进行编码；步骤4：依据每个图节点的编码进行过滤，生成查询图节点的候选集；步骤5：对生成的候选集进行二次过滤与验证。所述步骤1包括：步骤1.1：以每个节点本身作为树的根节点；步骤1.2：将当前节点的邻居节点插入树中作为当前节点的孩子节点，并标记为已访问；步骤1.3：访问当前节点的每个邻居节点，重复执行步骤1.2生成多棵当前节点的子树，直到遍历的层数达到预设层数时结束。所述步骤2包括：步骤2.1：将数据图中的同一种标签归入一个桶中；步骤2.2：将每个桶从1开始按顺序编号；步骤2.3：根据每个桶编号的二进制形式，将二进制数上第i位的值为1的所有桶归为第i组，得到组的标签桶组，所述步骤3包括：步骤3.1：对于每个图节点为根节点生成的树，以树的根节点为当前节点，初始化个以当前节点为根节点的树；步骤3.2：以步骤1生成的树的根节点为起始节点进行深度优先遍历；步骤3.3：根据节点标签所在的桶组将节点加入到相应桶组的树中；步骤3.4：重复执行步骤3.2～步骤3.3遍历完步骤1生成的树的所有节点后执行步骤3.5；步骤3.5：对当前图节点进行编码，包括：步骤3.5.1：将个树转化为邻接矩阵；步骤3.5.2：计算邻接矩阵的特征值，并记录前两个最大的特征值；步骤3.5.3：将当前图节点的标签、度以及个树的前两个最大的特征值作为当前节点的编码；步骤3.6：对于数据图、查询图上的所有图节点，重复执行步骤3.1～步骤3.5，生成每个图节点的编码。所述步骤4包括：步骤4.1：依次访问查询图节点，并将每个节点的编码与数据图中所有节点的编码进行比较；步骤4.2：选择出同时符合如下条件1)～3)的候选节点，并存入当前查询图节点的候选集中，其中条件1)～3)定义为：1)节点标签必须相同；2)查询图节点的度必须小于等于数据图节点的度；3)查询图节点生成的每棵标签树对应的特征值必须小于等于数据图节点生成的每棵标签树对应的特征值。所述步骤5包括：步骤5.1：选择查询图轴心的一个邻居作为当前查询图的起始节点，从轴心的候选集中随机选择一个节点作为轴心的候选节点；步骤5.2：依次访问当前查询图节点的候选节点的邻居；步骤5.3：将当前查询图节点以及一个候选节点存入匹配序列seq＝{(u1,v1),(u2,v2),…,(us,vj),…},s＝1,2,…,s,j＝1,2,…,m，其中，s表示查询图节点总数，m表数据图节点总数，us表示第s个查询图节点，vj表示与第j个查询图节点匹配的候选节点；步骤5.4：将当前查询图节点的邻居在匹配序列中的位置存入集合sq中；步骤5.5：将当前查询图节点已匹配的候选节点的邻居在匹配序列中的位置存入集合sg中；步骤5.6：验证sq是否是sg的子集，如果是，执行步骤5.7；如果不是，执行步骤5.8；步骤5.7：判断查询图节点是否全部访问完毕，如果是，记录轴心候选节点，运行结束；如果不是，执行步骤5.9；步骤5.8：查询轴心候选节点的邻居是否访问完毕，如果是，结束运行；如果不是，返回步骤5.2；步骤5.9：访问下一个查询图节点，重复执行步骤5.2～步骤5.6。本发明的有益效果是：本发明提出了一种基于编码树的gpu轴心子图匹配方法，对每个节点进行压缩编码，首先将节点的标签、度和邻居结构融入到多棵不同的编码树中，然后计算每个编码树的特征向量并保存，在查询图中仅需要比较查询图节点与数据图节点的特征向量编码，即可将数据图中的无效节点进行大规模的过滤，大大缩小了候选节点生成的搜索空间树的尺寸，加快了执行效率。本发明建立了一种新颖的多编码树方式，利用节点的标签、度以及节点邻居的结构特征组合对节点进行编码，在gpu上对查询图节点并行地进行剪枝，明显减少了数据图候选节点所生成的空间搜索树的尺寸，进而高效地完成轴心子图匹配搜索；本发明不仅在时间上对轴心子图匹配搜索进行了查询优化，而且对于计算资源和内存资源的消耗也大大减少。附图说明图1为本发明中的基于编码树的gpu轴心子图匹配方法流程图；图2为本发明中的两层无标签的树结构图，其中(a)表示以图节点u1为根节点的树，(b)表示以图节点v1为根节点的树，(c)表示以图节点v5为根节点的树；图3为本发明中的标签树结构图，其中(a)表示以图节点u1为根节点的两棵标签树，(b)表示以图节点v1为根节点的两棵标签树，(c)表示以图节点v5为根节点的两棵标签树；图4为本发明中的对图节点进行编码的流程图；图5为本发明中的二次过滤与验证流程图。具体实施方式下面结合附图和具体实施实例对发明做进一步说明。针对基于gpu的子图匹配方法会产生大量的内存资源浪费，而基于cpu的轴心子图匹配方法难以利用gpu等高度并行化的新硬件，本发明提供了一种基于编码树的gpu轴心子图匹配方法，首先需要找到与查询图匹配的所有子图，然后在子图中找到所有与查询图轴心匹配的节点，但是这些子图中所包含的轴心的匹配会存在重复节点，这样就产生了大量的不必要的中间结果，占用大量内存资源。基于cpu的轴心子图匹配方法是利用机器学习预测轴心的候选节点的类别，再根据相应的方法来验证预测的节点是有效节点还是无效节点，从而找到所有与轴心匹配的节点，但是在预测错误情况下会浪费大量的计算资源和内存消耗，并且难以有效利用gpu等新硬件的大规模并行处理能力。形式化定义本发明方法要解决的问题：给定一个查询图q＝{vq,eq,lq}，轴心up∈vq以及数据图g＝{vg,eg,lg}，轴心vp∈vg，存在一个单射函数f:vq→vg，轴心子图同构需要满足如下三个条件：(1)有f(u),f(v)∈vg且lq(u)＝lg(f(u))，lq(v)＝lg(f(v))；(2)有(f(u),f(v))∈eg；(3)up＝f(vp)。简而言之，就是在数据图中找到与查询图轴心标签相同的所有节点，并且每个节点至少存在于一个子图中，这个子图的结构与查询图结构相同且对应节点标签也相同。为解决上述问题本发明首先对查询图节点和数据图节点进行编码，通过比较查询图节点和数据图节点的编码来过滤节点，继而通过二次过滤和验证框架得到最终轴心子图匹配的结果。本发明提出的编码方式还充分考虑了gpu的特点，从而使gpu在利用编码进行过滤时可以充分地进行并行操作，将数据图中的无效节点进行大规模的过滤，大大缩小了候选节点生成的搜索空间树的尺寸，加快了执行效率。如图1所示，一种基于编码树的gpu轴心子图匹配方法，采用c 和cuda编程实现，包括：图节点的编码分为两个部分，首先根据节点邻居的结构特征，对节点周围的邻居生成一棵固定层数的树；其次是结合节点邻居的标签，将节点的一棵树分割成多棵树，如图2～3所示。步骤1：根据查询图、数据图节点的邻居节点结构将每一个节点生成一棵具有一定层数的树，包括：步骤1.1：以每个节点本身作为树的根节点；步骤1.2：将当前节点的邻居节点插入树中作为当前节点的孩子节点，并标记为已访问；步骤1.3：访问当前节点的每个邻居节点，重复执行步骤1.2生成多棵当前节点的子树，直到遍历的层数达到预设层数时结束。如果将给定图中的每个节点都生成一棵无标签树，可以过滤掉数据图中与查询图节点邻居结构不一致的节点，然而这种做法只考虑了邻居结构问题，而没有充分利用邻居的标签信息，想要高效的过滤节点必需尽可能多的考虑节点以及节点邻居的标签特征。如果图中共有n种标签，则可以设置不超过n个不同种类的桶，称作标签桶，将每种标签按一定形式(哈希、等分等)归入一种类别的桶中，不同种类的桶按顺序从1开始编号。将标签桶序号二进制形式第i位为1的所有标签桶归为第i组，共有组，这样一棵带有标签的树就涵盖了图中一半的标签，可以高效的过滤掉数据图中的候选节点。同一个标签桶组的所有标签类型的邻居节点将被用来生成同一棵树。其中，将标签放入标签桶中的方式并不唯一，除了上面提及的哈希、等分等形式还可以采用其他映射、分组等方式代替，存入标签桶组也可以采用二进制形式对应位置为0的情况代替。表1给出了一种等分方式对标签进行分类。表1分类结果标签种类abc桶编号123二进制表示011011步骤2：根据数据图中的标签种类生成组的标签桶组，其中n表示标签种类数，包括：步骤2.1：将数据图中的同一种标签归入一个桶中；步骤2.2：将每个桶从1开始按顺序编号；步骤2.3：根据每个桶编号的二进制形式，将二进制数上第i位的值为1的所有桶归为第i组，得到组的标签桶组，通过标签编码树的方式将邻居节点标签应用到邻居结构上，以增强过滤能力。事实上，每个节点都可以根据其邻居结构生成一棵无标签树。然而邻居节点的标签可能不同，仅生成无标签树无法进行有效的比较。因此需要根据标签类型对树进行切割，将同一标签桶组的节点放到一棵树中。对于查询图中的每一个节点的每个多编码树，在过滤过程中将其前两个特征值与数据图中的多编码树特征值进行比较。当数据图中的节点的顶点编码与查询图的节点的顶点编码符合如下条件才可以被存入查询图节点的候选集：(1)节点标签必须相同；(2)查询图节点的度必须小于等于数据图节点的度；(3)查询图节点生成的每棵标签树对应的特征值必须小于等于数据图节点生成的每棵标签树对应的特征值。步骤3：根据生成的组的标签桶组，将步骤1生成的每个图节点的树分割为个树并进行编码，如图4所示，包括：步骤3.1：对于每个图节点为根节点生成的树，以树的根节点为当前节点，初始化个以当前节点为根节点的树；步骤3.2：以步骤1生成的树的根节点为起始节点进行深度优先遍历；步骤3.3：根据节点标签所在的桶组将节点加入到相应桶组的树中；步骤3.4：重复执行步骤3.2～步骤3.3遍历完步骤1生成的树的所有节点后执行步骤3.5；步骤3.5：对当前图节点进行编码，包括：步骤3.5.1：将个树转化为邻接矩阵；步骤3.5.2：计算邻接矩阵的特征值，并记录前两个最大的特征值；步骤3.5.3：将当前图节点的标签、度以及个树的前两个最大的特征值作为当前节点的编码；步骤3.6：对于数据图、查询图上的所有图节点，重复执行步骤3.1～步骤3.5，生成每个图节点的编码。步骤4：对每个图节点的编码进行过滤，生成查询图节点的候选集，如图5所示，包括：步骤4.1：依次访问查询图节点，并将每个节点的编码与数据图中所有节点的编码进行比较；步骤4.2：选择出同时符合如下条件1)～3)的候选节点，并存入当前查询图节点的候选集中，其中条件1)～3)定义为：1)节点标签必须相同；2)查询图节点的度必须小于等于数据图节点的度；3)查询图节点生成的每棵标签树对应的特征值必须小于等于数据图节点生成的每棵标签树对应的特征值。二次过滤和验证是利用过滤与验证框架，将编码过滤后得到的每个查询图节点的候选集再次过滤。这次过滤是依据轴心子图同构的第二个条件，即如果两个查询图节点之间存在边，那么它们在数据图中的候选节点之间也必定存在边，否则该节点即可被过滤掉。过滤规则：给定查询图q和数据图g以及查询图节点的访问顺序，以查询图轴心为起始节点，依次访问轴心的邻居，数据图中同样以轴心候选节点为起始节点，依次访问邻居节点，这样就可以直接过滤掉与轴心候选节点之间不存在边的候选节点，同样地随后每一层的节点都必须是上一层已匹配节点的邻居。验证规则：给定查询图q和数据图g，将已匹配的查询图节点us以及其在数据图中的匹配节点vj存入匹配序列seq＝{(u1,v1),(u2,v2),…,(us,vj),…}。将当前查询图节点的邻居在匹配序列中的位置存入集合sq中，并将其匹配的数据图的节点的邻居在匹配序列中的位置存入集合sg中，匹配过程中必须满足sq是sg的子集。步骤5：对生成的候选集进行二次过滤与验证，包括：步骤5.1：选择查询图轴心的一个邻居作为当前查询图的起始节点，从轴心的候选集中随机选择一个节点作为轴心的候选节点；步骤5.2：依次访问当前查询图节点的候选节点的邻居；步骤5.3：将当前查询图节点以及一个候选节点存入匹配序列seq＝{(u1,v1),(u2,v2),…,(us,vj),…},s＝1,2,…,s,j＝1,2,…,m，其中，s表示查询图节点总数，m表数据图节点总数，us表示第s个查询图节点，vj表示与第j个查询图节点匹配的候选节点；步骤5.4：将当前查询图节点的邻居在匹配序列中的位置存入集合sq中；步骤5.5：将当前查询图节点已匹配的候选节点的邻居在匹配序列中的位置存入集合sg中；步骤5.6：验证sq是否是sg的子集，如果是，执行步骤5.7；如果不是，执行步骤5.8；步骤5.7：判断查询图节点是否全部访问完毕，如果是，记录轴心候选节点，运行结束；如果不是，执行步骤5.9；步骤5.8：查询轴心候选节点的邻居是否访问完毕，如果是，结束运行；如果不是，返回步骤5.2；步骤5.9：访问下一个查询图节点，重复执行步骤5.2～步骤5.6。当前第1页1 2 3
技术特征：1.一种基于编码树的gpu轴心子图匹配方法，其特征在于，包括：
步骤1：根据查询图、数据图节点的邻居节点结构将每一个节点生成一棵具有一定层数的树；
步骤2：根据数据图中的标签种类生成组的标签桶组，其中n表示标签种类数；
步骤3：根据生成的组的标签桶组，将步骤1生成的每个图节点的树分割为个树并进行编码；
步骤4：依据每个图节点的编码进行过滤，生成查询图节点的候选集；
步骤5：对生成的候选集进行二次过滤与验证。
2.根据权利要求1所述的一种基于编码树的gpu轴心子图匹配方法，其特征在于，所述步骤1包括：
步骤1.1：以每个节点本身作为树的根节点；
步骤1.2：将当前节点的邻居节点插入树中作为当前节点的孩子节点，并标记为已访问；
步骤1.3：访问当前节点的每个邻居节点，重复执行步骤1.2生成多棵当前节点的子树，直到遍历的层数达到预设层数时结束。
3.根据权利要求1所述的一种基于编码树的gpu轴心子图匹配方法，其特征在于，所述步骤2包括：
步骤2.1：将数据图中的同一种标签归入一个桶中；
步骤2.2：将每个桶从1开始按顺序编号；
步骤2.3：根据每个桶编号的二进制形式，将二进制数上第i位的值为1的所有桶归为第i组，得到组的标签桶组，
4.根据权利要求1所述的一种基于编码树的gpu轴心子图匹配方法，其特征在于，所述步骤3包括：
步骤3.1：对于每个图节点为根节点生成的树，以树的根节点为当前节点，初始化个以当前节点为根节点的树；
步骤3.2：以步骤1生成的树的根节点为起始节点进行深度优先遍历；
步骤3.3：根据节点标签所在的桶组将节点加入到相应桶组的树中；
步骤3.4：重复执行步骤3.2～步骤3.3遍历完步骤1生成的树的所有节点后执行步骤3.5；
步骤3.5：对当前图节点进行编码，包括：
步骤3.5.1：将个树转化为邻接矩阵；
步骤3.5.2：计算邻接矩阵的特征值，并记录前两个最大的特征值；
步骤3.5.3：将当前图节点的标签、度以及个树的前两个最大的特征值作为当前节点的编码；
步骤3.6：对于数据图、查询图上的所有图节点，重复执行步骤3.1～步骤3.5，生成每个图节点的编码。
5.根据权利要求1所述的一种基于编码树的gpu轴心子图匹配方法，其特征在于，所述步骤4包括：
步骤4.1：依次访问查询图节点，并将每个节点的编码与数据图中所有节点的编码进行比较；
步骤4.2：选择出同时符合如下条件1)～3)的候选节点，并存入当前查询图节点的候选集中，其中条件1)～3)定义为：
1)节点标签必须相同；
2)查询图节点的度必须小于等于数据图节点的度；
3)查询图节点生成的每棵标签树对应的特征值必须小于等于数据图节点生成的每棵标签树对应的特征值。
6.根据权利要求1所述的一种基于编码树的gpu轴心子图匹配方法，其特征在于，所述步骤5包括：
步骤5.1：选择查询图轴心的一个邻居作为当前查询图的起始节点，从轴心的候选集中随机选择一个节点作为轴心的候选节点；
步骤5.2：依次访问当前查询图节点的候选节点的邻居；
步骤5.3：将当前查询图节点以及一个候选节点存入匹配序列seq＝{(u1,v1),(u2,v2),…,(us,vj),…},s＝1,2,…,s,j＝1,2,…,m，其中，s表示查询图节点总数，m表数据图节点总数，us表示第s个查询图节点，vj表示与第j个查询图节点匹配的候选节点；
步骤5.4：将当前查询图节点的邻居在匹配序列中的位置存入集合sq中；
步骤5.5：将当前查询图节点已匹配的候选节点的邻居在匹配序列中的位置存入集合sg中；
步骤5.6：验证sq是否是sg的子集，如果是，执行步骤5.7；如果不是，执行步骤5.8；
步骤5.7：判断查询图节点是否全部访问完毕，如果是，记录轴心候选节点，运行结束；如果不是，执行步骤5.9；
步骤5.8：查询轴心候选节点的邻居是否访问完毕，如果是，结束运行；如果不是，返回步骤5.2；
步骤5.9：访问下一个查询图节点，重复执行步骤5.2～步骤5.6。
技术总结本发明提供一种基于编码树的GPU轴心子图匹配方法，对每个节点进行压缩编码，首先将节点的标签、度和邻居结构融入到多棵不同的编码树中，然后计算每个编码树的特征向量并保存，在查询图中仅需要比较查询图节点与数据图节点的特征向量编码，即可将数据图中的无效节点进行大规模的过滤，大大缩小了候选节点生成的搜索空间树的尺寸，加快了执行效率；本发明不仅在时间上对轴心子图匹配搜索进行了查询优化，而且对于计算资源和内存资源的消耗也大大减少。
技术研发人员：李传文;汪洋;谷峪;于戈
受保护的技术使用者：东北大学
技术研发日：2021.04.30
技术公布日：2021.08.03
