典型文献
多编码树GPU并行轴心子图匹配
文献摘要：
子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题.针对现在已经有许多高效的子图同构算法,然而对于轴心子图同构问题目前并没有基于GPU的搜索算法,且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出了一种基于GPU的轴心子图同构算法.首先,通过一种新颖的多编码树方式,利用节点的标签、度以及节点邻居的结构特征的组合对节点进行编码,并在GPU上对查询图节点并行地进行剪枝,从而明显地减小数据图候选节点所生成的搜索空间树的尺寸;然后,逐层访问查询图节点的候选节点,过滤掉不满足的节点;最后,验证得到的子图是否是查询图的同构子图,从而高效地完成轴心子图同构搜索.实验结果表明,与GPU友好子图匹配(GpSM)算法相比,所提算法的执行时间降低了二分之一,且该算法能够高效地执行轴心子图同构搜索并且具有可扩展性.所提轴心子图同构算法可以减少解决轴心子图同构问题所需的时间,同时降低了GPU内存消耗,提升了算法的性能.
文献关键词：
GPU;编码树;轴心子图同构;子图同构;并行加速
中图分类号：
作者姓名：
汪洋;江世杰;曹宇聪;李传文
作者机构：
东北大学计算机科学与工程学院,沈阳110169
文献出处：
引用格式：
[1]汪洋;江世杰;曹宇聪;李传文-.多编码树GPU并行轴心子图匹配)[J].计算机应用,2022(01):132-139
A类：
轴心子图同构,GpSM
B类：
编码树,GPU,子图匹配,多项式,NP,题目,搜索算法,图匹配问题,不必要,邻居,查询图,剪枝,小数据,所生,搜索空间,逐层,滤掉,是否是,执行时间,二分之一,可扩展性,少解,并行加速
AB值：
0.143761
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
