DGSM: A GPU-Based Subgraph Isomorphism Framework with DFS Exploration
DescriptionSubgraph Isomorphism is a fundamental problem in graph analytics and it has been applied to many domains. It is well known that subgraph isomorphism is a NP-complete problem. There has been a lot of efforts devoted to this problem in the past two decades. However, GPU-based subgraph isomorphism systems are relatively rare since the GPU memory is not big enough to hold all the instances during the matching process. Most current GPU subgraph isomorphism frameworks suffer from the limited GPU main memory and redundant computation. These issues restrict them on smaller patterns and graphs and limit their performance. To overcome these issues, we design a new GPU-based subgraph isomorphism system named DGSM. We validate our techniques by comparing with two state-of-the-art systems, CPU-based DAF and GPU-based GSI. Our experimental results show that our system achieve 2 orders of magnitude faster than DAF and GSI on both labeled and unlabeled graph.
Event Type
Workshop
TimeMonday, 14 November 202211:10am - 11:27am CST
LocationD221
W
Recorded