一种同构子图查询优化方法

摘要

本发明公开了一种同构子图查询优化方法，该方法是基于精确性同构子图查询中的经典算法VF2算法上进行的改进优化，由于VF2目前在大图的运用中查询代价过高，本发明在其基础上对其优化，分别从标签频率排序以及加速候选对寻找方案，以及利用稀疏矩阵代替原本二维矩阵来优化匹配对的存储方式等三个方面对其进行优化，提出一种新的同构子图查询优化方法。在新的优化方法中，首先，加速原有VF2算法的寻找候选对的方案降低其时间复杂度；其次，在数据导入时，按照标签出现的频率排序，优先匹配出现频率少的标签；最后，优化匹配对的存储方式，用稀疏矩阵代替原有矩阵。本发明公开的新的同构子图查询优化方法可以有效降低算法执行时间和递归次数，提高算法性能。

主权项

一种同构子图查询优化方法，其特征在于，包括如下步骤：1)输入查询图Q和数据图G，以及匹配映射函数M()，中间状态s,对查询图Q中标签的出现频率按从低到高的方式进行排序，在进行匹配的时候，优先匹配Q中出现频率低的标签；2)运用递归的方式进行数据图G的搜索匹配，在匹配初始化阶段，采用稀疏矩阵来代替VF2中的二维矩阵来构建边矩阵；搜索匹配时，优先匹配标签出现频率最低的点，在匹配其余点时，如果前驱或者后继出现多个，同样优先选择标签频率低的；3)查询图Q和数据图G进行匹配时，如果匹配映射函数M(s)包含了查询图Q中的所有点和边，则Q在数据图G中的同构子图找到，否则，需要在每次局部匹配基础上，进行后续点的匹配；4)在后续点的匹配中，首先找出所有可能进行匹配点对集合P(s)，然后对于查询图Q中的一个点与数据图G中所有点组成的匹配对中的每一个匹配对p，检查加入匹配p是否适应保证两图同构的可行性规则，如果不适应，则需要进入匹配点对集合P(s)中的下一匹配，直至找到适应可行性规则的p,然后将p加入M(s)，同时状态更新为s’，循环过程结束后，则存储其数据结构，并输出查询图Q和数据图G之间的映射关系，也就是查询图Q在G中的同构子图。