一种加速精确子图匹配的方法

1.一种加速精确子图匹配的方法，其特征在于，步骤包括：步骤S0：分解：对查询图进行多核分解，将一个大的查询图分解多个小的子图，所述小的子图被称为核，最终得到一个压缩图；步骤S1：得到辅助结构 ：根据查询图，先在数据图 进行裁剪，确定每一个查询图节点候选节点集，生成一个用于加速查询的辅助结构 ；步骤S2：生成查询的执行计划：根据辅助结构 生成查询的执行计划；所述查询的执行计划包括核间匹配顺序核和核内匹配顺序；步骤S3：初始化图缓存：根据用户给定的内存上限，初始化图缓存，以保证在执行查询的期间，内存使用不会超过给定的阈值 ；步骤S4：执行匹配过程：基于查询计划以及辅助结构 ，开始执行匹配过程，并最终得到结果；步骤S5：得到匹配结果：当图缓存足够大时，本身能够容纳所有的结果时，将图缓存的内容直接写入到磁盘中，作为匹配的压缩形式结果；所述步骤S1中，所述辅助结构 构建的流程包括：步骤S11：对于每个查询图节点 ，候选节点集 的计算，通过遍历每个数据图节点 ，检查 是否满足如下的约束：1）两个节点的标签相同，即 ；2）两个节点的邻接节点的标签数量分布也要满足 其中 为图中所有标签的集合， 为节点 的邻接节点标签为 的邻居集合，只有满足了这两个约束才能将节点 加入到候选节点集 中；步骤S12：对于查询图中的每条边 ，对于 ，如果在数据图中存在这样的一条边 ，那在辅助结构 中，为 中的两个节点 ，添加一条边连接，完成了辅助结构 的初始化；步骤S13：给定一个查询图节点的序列 ，对 进行裁剪，按照顺序每次取一个查询图节点 ，对于 中的任意一个节点 ，和 的任意一个邻居 ，如果在 中不存在这样的一个节点 与 相连接，那将 及其相连接的边从 中删除，表示节点 是不能与节点 相匹配的，从搜索的空间预先删除掉；步骤S14：重复步骤S13，直到 不再发生变化，或者重复其至一个指定的阈值，完成了辅助结构 的构建和裁剪；所述步骤S2中，所述查询计划生成的步骤包括：生成核间匹配顺序 的具体过程如下：1）对于每个核 ，其匹配结果数量由 ,第一个匹配的核选取为 ，将其加入到 中；其中， 为辅助结构中节点 的候选集的数量， 为核 的平均度数， 为核 的的节点数;2）依次选取 加入到 中，其中 为在压缩图中所有和 中的核相邻的节点集；对于每个核 的核内匹配顺序 ,生成的流程包括：1）对于第一个节点的选取，如果 在 上是第一个匹配的，那第一个节点的选取为 ；如果 在 上不是第一个匹配的，那第一个节点的选取为 ；其中 为 按照 顺序匹配的前一个核，然后将选取的第一个节点加入到 中；2）接着一次选取 加入到 中，其中 为在核 中所有与 中节点相邻的节点集；所述步骤S4中，匹配的过程和图缓存工作的流程包括：步骤S41：整个匹配过程分为核内匹配核和核间匹配，核内的匹配是从数据图中找到查询图对应的子图，并将其暂存到图缓存中；核间匹配是利用图缓存，如果命中，则直接从图缓存中获取局部的匹配结果；步骤S42：对于核间匹配的序列 ，在匹配一个核 时，按照 的核内匹配顺序 ；步骤S43：对于一个核 ，根据其对应的核内匹配的序列 进行操作；步骤S44：对于图缓存，进行插入删除作业；所述步骤S3中，在程序中内置了一个预设的块大小 ,当匹配过程中使用的块数量超过了总数 时，采用FIFO的淘汰策略，用来避免内存使用超过给定阈值。 2.根据权利要求1所述的加速精确子图匹配的方法，其特征在于，所述步骤S0中，通过一个查询图 分解为多个核的步骤包括：步骤S01：准备三个队列 , , ,分别用于存储已经分解好的核，待分解的查询图子图，以及核与核之间的桥梁节点，初始化为 , ；步骤S02：每次从 中取出一个查询图子图 ,遍历每个节点 ,尝试将 从 中去除掉，其中包括了所有和 相连接的边，如果这时， 被分解为两个不相连通的子图 , ，则将两个子图都加入到队列 中，同时将 加入到队列 ，否则就将其作为一个核放入到队列 中；步骤S03：一直重复步骤S02直到队列 为空， 和 中为查询图 对应的多核分解的结果，将两个队列中结果以压缩图的形式展示出来。 3.根据权利要求1所述的加速精确子图匹配的方法，其特征在于，所述步骤S42中关于图缓存的操作包括：（1）对于第一个匹配的查询图节点 ，首先生成一个三元组的查询键 ，其中 为数据图中一个能和 匹配的节点， 为核 预设的一个id，将三元组发送给图缓存执行查询操作，图缓存将返回数据图中所有能够和 匹配的且 与 相匹配的子图集合，记为 ，如果返回的结果为 ,则算法直接回溯剪枝，如果返回结果不为空，则遍历 ，每次取其中一个匹配结果加入到全局的部分匹配结果中，然后根据核间匹配的顺序 ，跳转到下一个待匹配的核 ；（2）对于最后一个匹配的查询图节点 ，根据辅助结构 ,通过遍历所有 的候选节点集，每次将 与候选节点集中的一个节点相匹配后，根据深度优先策略继续搜索，在回溯的过程，如果回溯的返回值为真，将当前整个 的局部匹配结果加入到图缓存中，完成图缓存的动态构建。 4.根据权利要求1所述的加速精确子图匹配的方法，其特征在于，所述步骤S43中，对于一个核 ，根据其对应的核内匹配的序列 ，包括以下的核内匹配过程：（1）对于第一个匹配的查询图节点 ,如果它在全局的部分匹配结果目前还没有匹配到节点，则其候选节点集为 ,每次取其中的一个节点继续按照深度优先的策略进行匹配，如果它在全局的部分匹配结果中，已经匹配到了结果，则直接使用该结果，继续按照深度优先的顺序遍历;（2）对于序列中其他的查询图节点 ，其候选节点集的计算通过 计算得出;其中 为按照匹配序列 ， 的邻居中先于其匹配的节点集， 为在辅助结构 中 中与 节点相连接的节点集合，意味当 与 匹配后， 的候选节点集合。 5.根据权利要求1所述的加速精确子图匹配的方法，其特征在于，所述步骤S44中，所述图缓存包括了由哈希表和链表构成的主体，以及管理块的队列 ，防止块淘汰的淘汰锁，进行插入删除作业的流程包括：（1）根据用户指定的阈值 和预设的块大小 ，初始化 个空的内存块，存入到一个队列 ，其中 的大小应当至少大于 中每个核的大小；（2）在插入一个结果时，根据读写头的块内偏移量和块大小，计算是否还有剩余空间存放该结果，如果有，则直接写入，读写头相应的后移，如果不够则向 申请一个新的块，继续存放，并将新的块与末尾的块链接起来，当 中没有新的块时，则执行淘汰策略，来回收一部分块用来分配新的块；（3）执行淘汰的策略，根据淘汰策略选取一个没有加淘汰锁的链表，然后直接依次遍历整个链表来执行删除回收操作；（4）如果 在执行淘汰策略时发现，剩下的所有链表都有淘汰锁，那么报错，提示需要分配更大的空间来存放更多的块。 6.根据权利要求1-5中任意一项所述的加速精确子图匹配的方法，其特征在于，所述步骤S5中，图缓存整体的结果为匹配结果的一种压缩形式，在解压缩时，具体过程包括：步骤S51：根据核间匹配的序列 ，从第一个核 的匹配结果出发，第一个核的匹配结果通过遍历查询键 , ，向图缓存查询，获取到匹配 所有的匹配结果，其中 为 中第一个匹配的查询图节点；步骤S52：对于解压缩过程中的每一个核 的匹配结果 ,加入到全局的部分匹配结果即 ，同时构建一个查询键 ，继续向图缓存查询，查询 的下一个核 的匹配结果；步骤S53：重复步骤S52，直到得到一个完整的匹配结果 。