基于ADD的图模式匹配双向模拟符号算法OA
Dual simulation symbolic algorithm for graph pattern matching based on ADD
针对如何优化双向模拟在执行过程中的逐一检查和更新问题,提出了一种基于代数决策图(ADD)的图模式匹配的双向模拟算法 GSDD.通过引入代数决策图符号化表示模式图和数据图,利用符号操作在内存计算中实现集合运算,即将结点的逐一处理改为多个结点并行处理,并使用一种同时处理自身结点和一步邻居的标签约束方法,优化双向模拟的候选集筛选.最后利用回溯算法对结点候选集进一步筛选.实验结果表明,与双向模拟相比,GSDD 算法可有效提高图模式匹配执行效率.
To optimize the sequential checking and update operations during dual simulation,this paper proposes a graph pattern-matching algorithm based on Algebraic Decision Diagram(ADD),namely GSDD,which optimizes the sequential checking and up-date operations during matching execution.The proposed GSDD algorithm employs algebraic decision diagrams to construct sym-bolic representations of both pattern graphs and data graphs.The algorithm performs symbolic set operations in memory,allowing multiple candidate nodes to be processed in parallel rather than sequentially.A novel label-constrained filtering strategy is further in-troduced to jointly process a node and its immediate neighbours,thereby improving candidate set pruning in dual simulation.Subse-quently,a backtracking strategy is adopted to further refine the candidate node set.Experimental results demonstrate that the pro-posed GSDD algorithm effectively improves graph pattern matching efficiency compared with the conventional dual simulation method.
余龙泉;徐周波;李上铨
桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004桂林电子科技大学 计算机与信息安全学院,广西 桂林 541004
信息技术与安全科学
图模式匹配双向模拟代数决策图并行处理标签约束
graph pattern matchingdual simulationalgebraic decision diagramsparallel processinglabel constraint
《桂林电子科技大学学报》 2026 (4)
372-378,7
国家自然科学基金(62362012)
评论