Fast Subgraph Matching on Large Graphs using Graphics Processors

Ha-Nguyen Tran, Jung-jae Kim, Bingsheng He
School of Computer Engineering, Nanyang Technological University, Singapore
Nanyang Technological University, 2015


   title={Fast Subgraph Matching on Large Graphs using Graphics Processors},

   author={Tran, Ha-Nguyen and Kim, Jung-jae and He, Bingsheng},



Download Download (PDF)   View View   Source Source   



Subgraph matching is the task of finding all matches of a query graph in a large data graph, which is known as an NP-complete problem. Many algorithms are proposed to solve this problem using CPUs. In recent years, Graphics Processing Units (GPUs) have been adopted to accelerate fundamental graph operations such as breadth-first search and shortest path, owing to their parallelism and high data throughput. The existing subgraph matching algorithms, however, face challenges in mapping backtracking problems to the GPU architectures. Moreover, the previous GPU-based graph algorithms are not designed to handle intermediate and final outputs. In this paper, we present a simple and GPU-friendly method for subgraph matching, called GpSM, which is designed for massively parallel architectures. We show that GpSM outperforms the state-of-the-art algorithms and efficiently answers subgraph queries on large graphs.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: