Many approaches have been proposed to solve subgraph matching problem based on lter-and-re ne strategy. The e ciency of those existing serial approaches relies on the computational capabilities of CPU. In this paper, we propose an RDF subgraph matching algorithm based on type-isomorphism using GPU since GPU has higher computational performance, more scalability, and lower price than CPU. Firstly, we present a concurrent matching model for type-isomorphism so that subgraph matching can be tackled in a parallel way. Secondly, we develop a parallel algorithm for capturing our proposed concurrent matching model and implement a prototype called IRSMG using GPU. Finally, we evaluate IRSMG on the benchmark datasets LUBM. The experiments show that IRSMG signi cantly outperforms the state-of-the-art algorithms on the CPU.
Subgraph matching, also known as subgraph isomorphism, is a widely known
NP-complete problem [
In this paper, we propose a parallel RDF subgraph matching on GPU and
implement a prototype called IRSMG (I nexact RDF S ubgraph M atching on
the G PU). where inexact RDF subgraph matching is a generalization of the
exact RDF subgraph matching [
LUBM.
The experiments show that IRSMG signi cantly outperforms the state-of-the-art methods approximately 4 times. 2
Concurrent matching model of subgraph matching Type-isomorphism Let G = (VG; EG; ; ) be a semantic graph (as an object graph) and GP = (VP ; EP ; ; ) be a connected semantic graph (as a subject graph), where labeling functions map to a common labeling alphabet; LV and LE are sets of discrete symbols; LVP LVG and LEP LEG . Let WP = (v0P ; e0P ; v1P ; : : : ; ekP 1; vkP ) be a k-edge walk over GP , where viP 2 VP and eiP 2 E.
Then a k-edge walk WG = (v0G; e0G; v1G; : : : ; ekG 1; vkG) over G is a type-isomorphic
match [
Type comparator C (va; vb) returns true if the labels for va and vb match, which also goes well for C (ei; ej ).
Basic graph pattern (BGP) query and its concurrent strategy BGP query [
Concurrently, BGP query can be decomposed into two basic operations: mapping and join [?]. Suppose that tp is a triple pattern in BGP query, which matches all the triples in RDF graphs, and let Etp be the candidate triple set that satisfy the condition in tp, this process of screening is called mapping. If a type-isomorphic walk with k length, the mapping set has k separate portions while all those sets have no relationship. Note that Etip and Etip+1 have the vertex whose id is the same. That is to say, the two triples shape a walk. If all Etip can conduct a walk with k-length then all the type-isomorphism of BGP query in RDF data graph are found.
Because the GPU cannot support dynamic memory allocation on the device memory during the execution of the GPU code, we will employ plain arrays as the main data structure. As to RDF graphs, each triple is composed of subject, predicate, and object. All elements in triples are string values (i.e. URIs and literal objects). When parsing a triple, both subject and object are treated equivalently while the predicate is treated separately. The dictionary is built to convert string values to integers. Therefore, we get a new quintuple: a set of label values associated with each vertex (also referred to subject and object) and another set of label values associated with each edge (predicate). Join Algorithm in GPU Join operation merges matched triples or partial matched graphs into a matched graph. The output of mappings is delivered to join if a BGP contains one or more shared variables. If a BGP has no shared variables, there is no reason to proceed next join operation. As to type-isomorphism, if two matched triples have a shared variable, they can be merged into a walk.
In order to make full use of parallelization advantages, the join process
contains three phases: mapping parallel, sort by join id, and reducing duplicate.
When mapping parallel, we set ag left or right according to the shared variable's
position in triples. The ag left or right contributes to reducing unnecessary
computation in the stage of reducing duplicate. GPU's single instruction multiple
data architecture [
Tp, stored as an ordered list of k segments.
Output: P, the set of matching walks in RDF. 1: InitWalks: Read a segment Sg from S.
If it matches the rst segment (S1; P1; O1) from WP , then convert Sg into a candidate walk of length 1. 2: for t = 2 to k 3: ExtendWalks: Read a segment Sg from S. If it matches the rst segment (St; Pt; Ot) from WP , then convert Sg into a candidate walk of length t.
Also read a candidate walk from the most recent candidate list.
4: Use bitonic sorting to order candidate walk
5: Reduce duplicate:
6: (Iterate over records with a given vertex key, sorted into two groups.)
7: Group 1, candidate walks of length t 1 from the ExtendWalks.
8: Group 2, segments Sg from the ExtendWalks mapper.
9: For each vertex key:
10: loop over all members of CandWalkList
11: If Cartesian product is non-null, then append Sg to make a candidate walk of
length t.
12: end loop
GPU-based Algorithm Algorithm 1 starts with InitWalks, which chooses
segments from an RDF graph S that matches the rst segment of the pattern Wp.
The loop beginning at line 2 runs a matching and join operation at each
iteration to extend candidate walks by one segment. The mapper emits segments
and walks with vertex ID as key. Matching is implemented in line 3. A bitonic
sort (line 4) [
Experiments and evaluations Our experiments were performed on a PC with a GTX590 GPU and an Intel Quad-Core CPU 2.66GHz running Ubuntu 14.04 64-bit. The main memory is 2GB, and the device memory of the GPU is 1536MB. We employ LUBM 4 as the benchmark dataset in our experiments to compare the performance with its CPU implementation in di erent dataset scale.
The experimental results are shown in Figure 1. With the increasing scale of data, the query time increases and the speedup grows up to four times. If computation is done on the GPU, data must be copied over the PCI express bus to the device and results have to be copied back. That explains the reason that queries on CPU is faster than queries on GPU when the scale of dataset is small.
As the increase of data scale, data transfer time between the device and the host takes smaller proportions of the whole process time, thus the query time increases while the growth rate becomes slower and slower.
6;000 0 cpu gpu
speedup
LUBLMU1BLMU2BLMU4BLMU8BLMU1B6LMU3B2M64 Acknowledgement. This work is supported by the program of the National Key Research and Development Program of China (2016YFB1000603) and the National Natural Science Foundation of China (NSFC) (61672377).