Name
Abstract | ||
|---|---|---|
Subgraph isomorphismis a well known NP-hard problem that finds all the matched subgraphs of a query graph in a large data graph. The state-of-the-art GPU-based solution is the vertex-oriented joining strategy, which is proposed by GSI. It effectively solves the problem of parallel write conflicts by taking vertices as processing units. However, this strategy might result in load-imbalance and redundant memory transactions when dealing with dense query graph. In this paper, we design a new storage structure Level-CSR and a new partition-oriented joining strategy. To avoid the influence of vertices with large degrees, we divide the dense vertices in traditional CSR into several GPU-friendly tasks and store them in Level-CSR. Then, an efficient execution strategy is designed based on the partitioned tasks. The partition strategy can improve the load imbalance caused by the irregularity of real-world graphs, and further reduce the redundant global memory access caused by the redundant neighbor set accessing. Besides, to further improve the performance, we propose a well-directed filtering strategy by exploiting a property of real-world graphs. The experiments show that compared with the state-of-the-art GPU based solutions, our approach can effectively reduce the number of unrelated candidates, minimize memory transactions, and achieve load balance between processors. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/978-3-030-60259-8_5 | Interational Conference on Web-Age Information Management |
DocType | Citations | PageRank |
Conference | 1 | 0.35 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jing Chen | 1 | 1 | 0.35 |
| Yu Gu | 2 | 201 | 34.98 |
| Qiange Wang | 3 | 1 | 1.71 |
| Chuanwen Li | 4 | 48 | 9.53 |
| Ge YU | 5 | 1313 | 175.88 |