论文部分内容阅读
图匹配问题本质上是一个图同构问题。给定一个查询图和数据图,图匹配问题是在数据图中求解所有同构于查询图的数据子图的过程。图匹配问题依据数据图结构是否随时间发生变化,分为静态图匹配和动态图匹配。随着现实世界中图规模不断增大,图匹配算法的效率愈呈现指数爆炸的增长,因此图匹配优化方法成为当前研究的热点。除此之外,随着这些领域的迅速发展,描述实体对象间关系图的结构会随着其发展而更新,目前已有动态图匹配方法存在存储代价和动态更新代价过高的问题。针对上述问题,本文通过对比当前主流的静态图匹配以及动态图匹配算法的优缺点,经过理论研究与实验论证,提出了适用于大规模查询图的静态图匹配优化方法与动态图匹配方法。本课题研究期间的主要工作如下:首先,本文介绍了当前主流的静态图匹配算法以及动态图匹配算法。通过进行大量实验分析,指出了当前主流方法中存在的缺陷;然后,通过分析查询图的结构与图匹配过程中的空间复杂度,结合最小连通支配集,提出了k查询节点路径,降低查询图中待匹配节点数,减小了图匹配过程迭代次数;提出了代价模型,在图匹配之前,为查询节点构造最优匹配顺序,优先匹配辨别程度高的节点,降低了后续节点候选集大小;根据查询图节点间的支配关系,针对查询图中被支配节点,提出有效剪枝规则,再次过滤假阳性候选集,得到最终结果集;考虑到在数据图发生改变时,传统静态图匹配算法无法满足动态图实时性,通过分析数据图更新部分与更新前后结果集的变化,对数据图节点分类,提出了基于映射-候选集-标签集的索引(MCL)以及层次路径索引(HP),避免了动态图匹配过程中大量的冗余计算。在数据图更新时,根据查询节点序列,缩小索引更新范围,采用增量式更新方式,仅更新局部索引,降低了重建索引的开销;最后对于动态图匹配过程与最小连通支配子图相结合,提高了动态图匹配效率。