Conference proceeding
GCSM: GPU-Accelerated Continuous Subgraph Matching for Large Graphs
2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp.1046-1057
05/27/2024
DOI: 10.1109/IPDPS57955.2024.00097
Abstract
Continuous subgraph matching (CSM) is a key building block in many graph mining applications. Previous research has primarily focused on CSM algorithms on CPU. However, due to the dynamic nature of input graphs and the data movement bottlenecks, it has been challenging to efficiently run CSM on heterogeneous systems with GPUs. This work proposes the first system that exploits GPU to accelerate CSM. The main idea of our system is to cache the frequently accessed graph data in GPU memory so that most of the data communication between CPU and GPU can be avoided during the matching process. To identify the frequent data, we propose an efficient frequency estimation technique based on random walks on the input graph. We also provide an end-to-end design that achieves efficient dynamic graph updates on the CPU and efficient incremental matching on the GPU. The experiments show that our system significantly improves the performance of CSM compared to existing CPU solutions and supports CSM on extremely large graphs.
Details
- Title: Subtitle
- GCSM: GPU-Accelerated Continuous Subgraph Matching for Large Graphs
- Creators
- Yihua Wei - University of IowaPeng Jiang - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- 2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp.1046-1057
- Publisher
- IEEE
- DOI
- 10.1109/IPDPS57955.2024.00097
- ISSN
- 1530-2075
- eISSN
- 1530-2075
- Grant note
- NSF: CNS-2311610
This work was supported by NSF award CNS-2311610.
- Language
- English
- Date published
- 05/27/2024
- Academic Unit
- Computer Science
- Record Identifier
- 9984658348302771
Metrics
4 Record Views