基于坐标映射及多重图划分的图相似查询研究

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

作者：刘哲峰;';梁平;';顾进广;'

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

摘要：图相似查询是图数据库资源管理最重要的操作之一。 目前的相似性查询算法几乎都是采用对整个图数据库进行过滤得到候选集的方式,没有考虑在实际图数据库中各数据图规模之间存在着一定的差距,没有必要对整个图数据库进行计算。 因此,提出了一种基于坐标映射的批量处理方式,从规模上对数据图进行剔除,使得后续需要计算的数据图数量大大减少。 同时给出了一个参数化的、基于选择性划分的 GED 下界,使得图划分方式具有约束性,而不是随机的,并在此基础上给出了一个多层索引结构,用于 GED 下限交叉检查。 模拟实验结果表明,所提出的处理方法在通过坐标映射来尽量缩减计算时间的同时,较好地提升了过滤精度,甚至能在过滤阶段就得到相似查询的结果。

关键词：图数据库;图相似查询;坐标映射;选择性图划分;多层索引结构