论文部分内容阅读
子图匹配是图算法研究的一个主要问题。子图匹配问题的定义是给出查询图,从大图数据库中找到与查询图结构相同且节点标签相同的所有子图。但在实际的应用中,用户往往只关心一些匹配得分较高的结果。因此便引入了Top-K子图匹配问题。Top-K子图匹配问题与子图匹配问题相似,不同之处在于Top-K子图匹配问题会对结果进行排序,最终返回k个得分较高的子图。因此对于返回全部子图匹配的问题,Top-K子图匹配问题显得更有针对性。本文针对图数据处理中的Top-K子图匹配查询进行研究,具体研究内容如下。首先,子图匹配方法主要采用过滤-验证模式进行查询,则过滤效果和验证效果将是影响算法效率的两个主要因素。通过对现有的子图匹配问题处理方法的分析,发现在过滤阶段现有方法主要存在以下问题:(1)等价节点重复枚举问题;(2)基于路径结构过滤开销过大的问题;(3)匹配顺序不当问题。在验证阶段则存在大量冗余验证问题。其次,在过滤阶段,提出PFilter算法,针对等价节点重复枚举问题,提出图压缩策略,将等价节点压缩从而减少枚举。针对基于路径过滤开销过大的问题,提出只考察直接邻居作为过滤方法,从而减少开销。针对匹配顺序不当问题,提出对查询图中候选节点最少的节点作为匹配起始节点,向图的两端进行深度优先探查。再次,在验证阶段,提出PGet Score算法,针对造成大量冗余验证的问题,提出利用RWM(ranking while matching)思想,对算法进行提前终止,从而减少冗余验证。最后,通过实验从处理时间、压缩节点数目等方面对本文提出的方法的高效性进行了验证。