[VLDB 2012]Efficient Subgraph Matching on Billion Node Graphs

重点了解实现star-join的具体过程。

分解query和STwigs排序

文中把star叫做STwigs，每一个STwigs查询为\(q=(r, L)\)，其中r是跟节点标签，L是子节点标签合集。
点的选择性：\(f(v)=deg(v)/freq(v.label)\)

分解算法：

每次取边都要保证两点的选择性和最大。第一次取两点，后续取结果中的点的邻居。

先处理原本在结果内的点，以该点为根生成star，添加进结果中，删除查询图中该star里的所有边。

如果这时选的另一个点度不是0（不只有上一个点这一个邻居），则也以该点为根生成star加入结果删除查询图中star里的边

删除查询图中度为0的点。

重复上述过程，直到查询图中不再有边。由于每次都是选择选择性最大的两个点，因此也完成了排序。

匹配

根据顺序，第一个STwig匹配data图中的标签，每个点能得到一组匹配的绑定点，然后匹配下一组。如果下一组的根节点在之前的匹配中出现过了，则直接使用之前的绑定结果，继续匹配子节点。如果下一组根节点没出现过，则会搜索所有该节点的标签相同节点作为绑定结果。重复操作直到所有查询点都被绑定。这时，每个STwig q都有一组绑定结果G(q)。需要说明的是其中的结果并非所有点的绑定候选的排列组合，需要用图的算法确定。