Publication Type
Journal Article
Version
acceptedVersion
Publication Date
9-2022
Abstract
Subgraph enumeration is important for many applications such as network motif discovery, community detection, and frequent subgraph mining. To accelerate the execution, recent works utilize graphics processing units (GPUs) to parallelize subgraph enumeration. The performances of these parallel schemes are dominated by the set intersection operations which account for up to $95\%$ of the total processing time. (Un)surprisingly, a significant portion (as high as $99\%$) of these operations is actually redundant, i.e., the same set of vertices is repeatedly encountered and evaluated. Therefore, in this paper, we seek to salvage and recycle the results of such operations to avoid repeated computation. Our solution consists of two phases. In the first phase, we generate a reusable plan that determines the opportunity for reuse. The plan is based on a novel reuse discovery mechanism that can identify available results to prevent redundant computation. In the second phase, the plan is executed to produce the subgraph enumeration results. This processing is based on a newly designed reusable parallel search strategy that can efficiently maintain and retrieve the results of set intersection operations. Our implementation on GPUs shows that our approach can achieve up to $5$ times speedups compared with the state-of-the-art GPU solutions.
Keywords
Graphics processing units, Acceleration, Pattern matching, Data structures, Instruction sets, Runtime, Data mining, Subgraph enumeration, GPU, Reuse
Discipline
Databases and Information Systems | Numerical Analysis and Scientific Computing
Research Areas
Data Science and Engineering
Publication
IEEE Transactions on Knowledge and Data Engineering
Volume
34
Issue
9
First Page
4231
Last Page
4244
ISSN
1041-4347
Identifier
10.1109/TKDE.2020.3035564
Publisher
Institute of Electrical and Electronics Engineers
Citation
GUO, Wentiao; LI, Yuchen; and TAN, Kian-Lee.
Exploiting reuse for GPU subgraph enumeration. (2022). IEEE Transactions on Knowledge and Data Engineering. 34, (9), 4231-4244.
Available at: https://ink.library.smu.edu.sg/sis_research/7130
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/TKDE.2020.3035564
Included in
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons