多级过滤与分区均衡的图相似搜索研究

来源：计算机技术与发展杂志2025年第07期北京时间：

作者：赵旭;梁平;顾进广;高峰;

单位：1. 武汉科技大学 计算机科学与技术学院,湖北 武汉 430065;2. 智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉 430065

摘要：图相似搜索指根据图编辑距离,从图数据库中搜索与查询图满足阈值要求的数据图集合的过程。 由于图编辑距离的计算是 NP-hard 问题,因此目前主流的图相似搜索算法主要采用“过滤-验证”框架。 而其中的过滤算法也仍然是基于分区索引的思想,存在分区过滤过程中过滤下界不紧密、候选集规模大、过滤耗时长和分区大小不均衡等问题。 因此提出了对图相似搜索算法相应的改进策略。 首先,在整个过滤阶段采用多级过滤的方式,按照代价由低到高的顺序,依次采用图大小、标签,顶点和邻边标签组以及分区索引进行逐级过滤,逐步筛选掉不符合阈值要求的数据图,以减少候选集生成开销;其次,给出了一种启发式方法来指导分区的初始顶点选择,以确保最终的分区尽量均衡,提高分区过滤下界的紧密性。 实验结果表明,提出的改进策略不仅可以提高过滤下界的紧密性、降低分区索引构建代价及减少候选图的生成数量,而且缩短了过滤阶段时间及图相似搜索的总体时间。

关键词：图相似搜索;图编辑距离;多级过滤;分区索引;分区均衡性