[发明专利]大图数据库中基于集合相似度的子图匹配方法

摘要

本发明公开了一种大图数据库中基于集合相似度的子图匹配方法，包括以下步骤1)在查询图的多个支配集中选取一个经济的支配集；2)集合相似度剪枝运用集合相似度剪枝方法得到查询顶点的所有候选点；3)基于结构的剪枝；根据查询图Q同构的结构限制，对查询顶点的所有候选点基于结构剪枝，过滤查询顶点的候选点；4)基于支配集的子图匹配。本发明提出一种有效的双图剪枝方法，包括集合相似度剪枝和基于结构的剪枝，通过本方法将检索出那些与查询图同构，同时满足运用动态加权集相似度的顶点匹配条件，有效提高查询效率。

主权项

一种大图数据库中基于集合相似度的子图匹配方法，其特征在于，包括以下步骤：1)在查询图的多个支配集中选取一个有效率的支配集，所述有效率的支配集包含最少的支配顶点数，且每个支配顶点的候选点数是最少的；2)集合相似度剪枝：运用集合相似度剪枝方法得到查询顶点的所有候选点；3)结构剪枝：根据查询图Q同构的结构限制，对查询顶点的所有候选点基于结构剪枝，过滤查询顶点的候选点；4)基于支配集的子图匹配：4.1)将查询图Q转化为支配查询图；4.2)在数据图G中找出支配查询图的所有匹配，即QD和G的子图间的映射M(QD)；4.3)找出查询图Q的所有子图匹配：将每个支配查询图QD的匹配扩展为查询图Q的子图匹配；如果当前状态M(s)覆盖了Q的所有顶点，则按照当前状态M(s)输出映射M(Q)；否则，对每个未覆盖的非支配顶点u′，考虑u′的1‑hop和2‑hop的邻近支配顶点，然后检查是否有候选对(u′,v′)满足集合相似度的子图匹配的条件，若是，则该候选对添加到当前状态中；遍历结束后，按照当前状态M(s)输出映射M(Q)。