.png){kind=icon}
返回
SGSI - A Scalable GPU-Friendly Subgraph Isomorphism Algorithm
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2022.3230744.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Due to the inherent hardness of subgraph isomorphism, the performance is often a bottleneck in various real-world applications. We address this by designing an efficient subgraph isomorphism algorithm leveraging features of GPU architecture. Existing GPU-based solutions adopt two-step output scheme, performing the same join twice in order to write intermediate results concurrently. They also lack GPU architecture-aware optimizations that allow scaling to large graphs. In this article, we propose a Scalable GPU-friendly subgraph isomorphism algorithm, SGSI. SGSI incorporates a Prealloc-Combine strategy based on the vertex-oriented framework, which avoids joining-twice in existing solutions. It uses a GPU-friendly data structure (called PCSR) to represent an edge-labeled graph. We also study fine-grained load balance strategies and discuss how to handle enormous graphs that cannot be resident in GPU memory. A partition-based pipeline framework is proposed. Extensive experiments on both synthetic and real graphs show that SGSI outperforms the state-of-the-art algorithms by up to several orders of magnitude and has a good scalability with graph size scaling to billions of edges.
Keyword:
SGSI
GPU
subgraph isomorphism
scalability
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
分享收藏
Mineralogy and crystal chemistry of Mn, Fe, Co, Ni, and Cu in a deep-sea Pacific polymetallic nodule
OAAI
OAAI分享收藏
查看更多内容