杨凌林关于子图匹配执行加速的论文《CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination》被 VLDB 2026 接收。

子图匹配是图分析中的一项基础问题，具有广泛的应用场景。然而，由于其固有的 NP-hard 特性，在大规模真实图上高效枚举子图匹配结果仍然极具挑战性。现有大多数工作采用基于深度优先搜索（DFS）的回溯策略，在搜索树的一条分支上以 DFS 的方式逐步扩展部分嵌入，直到找到一个完整嵌入，或无法继续扩展为止。该范式的一个主要局限在于枚举过程中会产生大量重复计算，从而显著增加整体运行时间。为了解决这一问题，我们提出了一种新的子图匹配算法 CEMR。该算法结合了两种减少重复扩展的技术：一是公共扩展合并，通过黑白顶点编码来实现；二是公共扩展复用，利用公共扩展缓冲区来完成。此外，我们还设计了两种剪枝技术，用于提前丢弃无效的搜索分支。在真实世界数据集和多样化查询负载上的大量实验结果表明，CEMR 在性能上优于现有的子图匹配方法。