GPU-Accelerated Batch-Dynamic Subgraph Matching
Authors:
- 13 May 2024
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 3204-3216
Abstract
Subgraph matching has garnered increasing attention for its diverse real-world applications. Given the dynamic nature of real-world graphs, addressing evolving scenarios with-out incurring prohibitive overheads has been a focus of research. However, existing approaches for dynamic subgraph matching often proceed serially, retrieving incremental matches for each updated edge individually. This approach falls short when handling batch data updates, leading to a decrease in system throughput. Leveraging the parallel processing power of GPUs, which can execute a massive number of cores simultaneously, has been widely recognized for performance acceleration in various domains. Surprisingly, systematic exploration of subgraph matching in the context of batch-dynamic graphs, particularly on a GPU platform, remains untouched. In this paper, we bridge this gap by introducing an efficient framework, GAMMA (GPU-Accelerated Batch-Dynamic Subgraph Matching). Our approach features a DFS-based warp-centric batch-dynamic subgraph matching algorithm. To ensure load balance in the DFS-based search, we propose warp-level work stealing via shared memory. Additionally, we introduce coalesced search to reduce redundant computations. Comprehensive experiments demonstrate the superior performance of GAMMA. Compared to state-of-the-art algorithms, GAMMA showcases a performance improvement up to hundreds of times.Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- DPTL+: Efficient Parallel Triangle Listing on Batch-Dynamic Graphs2021
- GSI: GPU-friendly Subgraph Isomorphism2020
- faimGraph: High Performance Management of Fully-Dynamic Graphs Under Tight Memory Constraints on the GPU2018
- Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs2018
- Logarithmic Radix Binning and Vectorized Triangle Counting2018
- Autonomous, independent management of dynamic graphs on GPUs2017
- cuSTINGER: Supporting dynamic graph algorithms for GPUs2016
- Network Motif Discovery: A GPU ApproachIEEE Transactions on Knowledge and Data Engineering, 2016
- Toward continuous pattern detection over evolving large graph with snapshot isolationThe VLDB Journal, 2015
- A (sub)graph isomorphism algorithm for matching large graphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004