Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration

vldb26-1881 · Experiment, Analysis & Benchmark (EA&B) · Tao Yu, Zhijie Zhang, Weiguo Zheng, Jeffrey Xu Yu, Qiang Zhou, Chuntao Hong
Abstract

Subgraph matching is a fundamental yet NP-hard problem in graph algorithms. Modern multi-core shared-memory architectures present substantial opportunities to accelerate subgraph matching through parallelism. However, while several parallel subgraph matching algorithms have been proposed, it warrants a systematic empirical study to evaluate: (1) the interaction effect of different parallel strategies, (2) their scalability, (3) underlying performance factors, and (4) the potential for efficiently parallelizing existing sequential algorithms. In this paper, we present a comprehensive study of parallel subgraph matching by analyzing three key components: task splitting, task scheduling, and match enumeration. To investigate their interplay, we evaluate 100 feasible combinations of representative techniques for each component. We further assess scalability across varying thread counts and explore performance variations under diverse query and data graph characteristics.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy