基于增量的动态图模式匹配符号算法研究

作     者：许昌胜 

作者单位：桂林电子科技大学 

学位级别：硕士

导师姓名：徐周波

授予年度：2023年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：动态图匹配 代数决策图 符号技术 邻域约束 ZSymbi 

摘      要：图作为一种可以描述事物之间关系的数据结构,在现实生活中应用广泛。子图匹配问题是图数据分析研究中的基本课题,有着十分重要的研究价值。但随着数据规模越来越大并且伴随实时变化,基于快照模式的动态图匹配算法无法满足实时响应的要求。基于辅助索引结构的动态图匹配算法能够在数据图发生变化时基于辅助结构的信息进行局部更新,获得比快照模式更快的求解效率。我们从两个方面对现有的动态图匹配技术进行优化,一方面优化辅助结构的候选集存储,通过为辅助结构添加更多的约束来优化辅助结构的存储空间,另一方面引入新的压缩技术,其中代数决策图是一种存储紧凑且易于操作的隐式存储结构,可以在相对较小的存储空间内实现大规模图的运算。本文引入代数决策图技术研究了动态图匹配符号算法以及考虑邻域约束解决现有算法中存在的信息冗余问题。主要研究成果和结论如下:(1)针对现有的动态图匹配算法数据图规模庞大,求解过程产生大量的内存消耗的问题,本文引入了代数决策图(Algebraic decision diagram,ADD)结构作为数据的表示方式,实现数据查询与更新的并行运算以及公共子图的共享存储,有效平衡了算法的空间和时间效率。(2)针对(1)中随着数据规模的快速增长,基于增量的有界模拟图匹配算法在更新过程中存在大量的重复计算,以及通过逐点扩展的方式确认受影响区域时的算法效率低下问题,本文基于ADD提出了一种新的编码方式来构建辅助索引结构ADD Index(AIndex),该辅助结构不仅可以压缩存储节点间的路径信息,同时可以利用ADD并行操作的特性,实现快速查找和维护;其次为了增量维护辅助结构和匹配结果,提出了适用于AIndex的增量更新算法。实验表明,与经典算法相比,优化了存储空间,求解性能有了明显提升。(3)为了降低动态子图匹配候选集空间和提高算法效率,针对目前最先进的增量子图同构匹配算法Symbi中的索引结构动态候选空间(Dynamic Candidate Space,DCS)中存在的信息冗余问题,引入邻域信息约束,提出了一种新的索引结构ZDCS,并提出了ZDCS的更新算法INCZDCS来动态维护ZDCS索引结构和匹配结果,进一步提出了动态图的增量子图匹配算法ZSymbi。最后,在真实数据集上与Symbi算法进行实验对比,结果表明ZSymbi有效缩减了计算空间并提高了算法的求解效率。