Technical Papers Archive

BMS2: Fast Batched Subgraph Matching on GPUs with Structure-Aware Scheduling


Authors: Jiayue Hu, Ke Meng, Zhiheng Lin, and Guangming Tan (Institute of Computing Technology (ICT), Chinese Academy of Sciences (CAS))

Abstract: Batched matching is widely used in drug discovery, software analysis, and social network analysis. Its core operation, subgraph matching, is an NP-complete graph algorithm that has been optimized in the HPC field for decades. As for batching scenario, we find that current subgraph matching systems are unable to leverage the common structure patterns of real-world graphs, thereby missing potential optimization opportunities. In this paper, we propose BMS2, a batched matching system with structure-aware scheduling. BMS2 incorporates these intrinsic properties into previous general filter-join strategy: (1) in the filter phase, BMS2 utilizes the presence information of special structure for early termination; (2) in the join phase, we exploit the similarity of batched queries to reuse matching results of common structure. Experiments demonstrate that BMS2 can achieve an order of magnitude performance improvement on GPUs compared to the state-of-the-art with the ability to process two orders of magnitude larger dataset.


Presentation: file

Back to Technical Papers Archive Listing