当前位置: 代码迷 >> 综合 >> 《Turbo iso: towards ultrafast and robust subgraph isomorphism search in large graph databases》读后笔记
  详细解决方案

《Turbo iso: towards ultrafast and robust subgraph isomorphism search in large graph databases》读后笔记

热度:83   发布时间:2023-12-14 06:10:25.0

用了几天时间看完了turboISO,第一感觉是要比VF2“先进”很多的,在以下几个方面有更多的考虑:1)起始点的选择。2)NEC树节点的匹配顺序。还引入了一些概念:1)NEC节点以及NEC树。2)CR,候选区域。我们结合算法流程讲解这些概念,下面是算法的overview

算法首先在查询图中确定一个起始点,记作us(line 1),接着把查询图重写为一棵NEC树(line 2),然后对于数据图中与起始点有相同label的点,记作vs(line 3)进行遍历(line 4 - line 9),遍历的计算过程是首先从vs出发进行CR探索(line 4),如果探索不成功,说明这个vs是不可行的,尝试下一个vs(line 5)。如果探索成功,那么说明NEC树的每一个节点都可以在这个候选区域中有一个候选子区域,也就是CR中有元素,但是这还不足以找到解。接着根据CR的情况以及NEC树确定NEC树中节点的匹配顺序(line 6),然后就是递归确定映射关系了(line 7 - line 9)。