面向图相似性搜索的高效图编辑距离算法

摘要：

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能.针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法.该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射.最后,将改进的图编辑距离算法扩展应用于图相似性搜索.在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49％,速度提升了约29％.

关键词：图编辑距离、等价映射、映射编码、下界计算、图相似性搜索

所属期刊栏目：40

分类号：TP391(计算技术、计算机技术)

资助基金：江苏省高校自然科学研究项目;江苏省高校优势学科建设工程资助项目

在线出版日期：2023-03-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：371-377