实验室动态

[2020 ICDE] GSI: GPU-friendly Subgraph Isomorphism

    曾立关于 GPU 加速子图同构算法的论文 (GSI: GPU-friendly Subgraph Isomorphism) ICDE 2020 录用.

    子图同构是一个著名的 NP-hard 难题,常见于社交网络分析和知识图谱查询等应用场景中。由于子图同构本身的计算复杂度较高,在各种真实应用中其性能往往是瓶颈所在。通过利用 GPU 特性(比如高并发的能力,显存的层级结构),我们设计了一种有效的子图同构算法来解决性能问题。

    已有的基于 GPU 的子图同构算法都采用了 two-step output scheme,通过把同样的表拼接过程做两次来解决并行写入中间结果的问题。此外,它们也缺少基于 GPU 体系结构的优化,因此很难被应用于大图上。

    在这篇论文中,我们提出了一种适合 GPU 的子图同构算法 GSI。与以往基于边拼接的 GPU 方法不同,我们提出了一种基于点拼接的 Prealloc-Combine 策略,因此无须重做拼接过程。同时,我们也设计了一种新的适合 GPU 的数据结构(PCSR),用来存储带边标签的图。在真实图和人工图上的一系列实验证明了 GSI 算法的有效性。GSI 不但比已有的方法快了几个数量级,而且有较好的扩展性,可以处理含数亿条边的图。