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