VSGM: View-Based GPU-Accelerated Subgraph Matching on Large Graphs
Guanxian Jiang, Qihui Zhou, Tatiana Jin, Boyang Li, Yunjian Zhao, Yichao Li, James Cheng
Abstract
Subgraph matching is a fundamental building block in graph analytics. Due to its high time complexity, GPU-based solutions have been proposed for sub graph matching. Most existing GPU-based works can only cope with relatively small graphs that fit in GPU memory. To support efficient subgraph matching on large graphs, we propose a view-based method to hide communication overhead and improve GPU utilization. We develop VSGM, a sub graph matching framework that supports efficient pipelined execution and multi-GPU architecture. Ex-tensive experimental evaluation shows that VSGM significantly outperforms the state-of-the-art solutions.
Topics & Concepts
Computer scienceMatching (statistics)Parallel computingCUDAGraphOverhead (engineering)Block (permutation group theory)Factor-critical graphGeneral-purpose computing on graphics processing unitsAnalyticsInduced subgraph isomorphism problemTheoretical computer scienceLine graphCombinatoricsData miningMathematicsGraphicsProgramming languageVoltage graphComputer graphics (images)StatisticsGraph Theory and AlgorithmsAdvanced Graph Neural NetworksNetwork Packet Processing and Optimization