Research Of Many-Core-Based Subgraph Matching Algorithm

In the time of big data, the scale and complexity of information are in exponential growth. The representation of information is becoming more complex. Graph provides a natural data structure, as a common model. So, graph plays an irreplaceable role in the time of big data. In large scale graph, it is important to carry out data mining and retrieve the required information. It is difficult for tradition CPU hardware platform to provide efficient computing speed. In the area of high performance compute, GPU is a common many-core platform for its high parallelism and multiple threads. In this paper, we implement a high efficiency subgraph matching algorithm for large scale graph with the GPU platform. The algorithm first finds the vertex in the large graph with the same properties as the central vertex of the query graph by GPU. And then we taking these found vertices center vertex, intercept subgraphs in the large graph by the algorithm of single source shortest path. Last we try to match the intercepted graphs to the query graph and confirm which one can be matched properly. The main work accomplished in this paper is as the following:(1)In the process of intercepting subgraphs, we propose a “unidegree” data preprocess. After the preprocess, data will be of better locality and threads’ work will be balanced. Another preprocess is the data transfer, the transmission delay time will be reduced by which.(2)In the parallel GPU program, atomic operation is used to avoid write and read error. However, the atomic operations down the compute speed. So we propose to use “data block iteration” instead of atomic operation. Data block iteration not only guarantees the accuracy but also improves the compute speed.(3)In the process of subgraph matching, we not taking too much pre-calculate, just make full use of the GPU’s many-core, match each pair vertex by VF2 algorithm concurrently to speed up the process of match.