曾立关于 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 不但比已有的方法快了几个数量级，而且有较好的扩展性，可以处理含数亿条边的图。