186
Y. Sun et al.
one-hop traversal from b 1 , triple instance [b 1 , [e 5 , a 1 ]] is written into the results
of q 1 . Then, a 1 is obtained and set as an initial vertex on (1), because a 1 is not
included into the key of temp results. Due to RE q1 ∩ iN F T =?A, iE ?A (e 5 ),
triple instance [a 1 , [e 5 , b 1 ]] is written into the results of q 1 , and [a 1 , [e 7 , f 1 ]] is
written into temp results through one-hop traversal from a 1 . Finally, final results
of q 1 are carried out because b 1 has included into results of q 1 .
The processing of obtained results of q 1 , q 2 , and q 3 are similar to q 1 . Through
M-PM algorithm, the results of multiple BGP graphs can be obtained by one
traversal of data graphs.
4 Experimental Evaluation
Query Sets. In the selection of query sets, residual edges of query node are an
important factor. In the D-Tree of query graphs, the residual edges of non-leaf
query node are associated with overlapped query subgraphs. As the depth of
D-tree increases, the closer to root node are and the more times the query node
overlap. Therefore, the multiple query graphs with the same and different depths
are selected into our query sets.
Datasets. A simulated dataset is selected in our experimental analysis. DBpedia 2015A
1 describes the information of sports and sport events. It contains
30,000 RDF triple instances with 20 triple patterns. Due to the small number of
triple patterns, it is different for DBpedia 2015A to reflect the benefits of multipattern matching algorithm. Therefore, a simulated dataset based on DBpedia
2015A is created, which contains almost 3 million RDF triple instances with 300
triple patterns.
Configurations. All experiments were performed on the Intel Xeon 5118 processor with 24GB RAM. The system is equipped with main memory, and it runs
a 64-bit Linux 3.13.0 kernel.
In this experimental analysis, we look at the multi-pattern matching with
same and different depth of D-Tree on simulated dataset.
Basic line (BL for short) algorithm is compared with M-PM algorithm. The
idea of BL algorithm is to reduce the size of original RDF graph by query parent
node and response query child node on reduced RDF graph. However, it does
not avoid the rematching on the overlapped RDF subgraphs between parent
and child node. Assumed that the size of multiple BGP graphs is n and the
quantity of data graphs is m (quantity statistics of triple instance). The time
complexity of BL algorithm is similar to O(n · m). And the time complexity
of M-PM algorithm is approximatively O(m) + O(log
n
m · m). Therefore, M-PM
algorithm is better time-efficient than basic line algorithm.
Figure 4a describes the execution time on different widths of D-Tree with
same depth. Figure 4b depicts the execution time on different depths of D-Tree
with same width. The root query node contains 80 triple patterns, and each child
node has 10 edges more than its parent node. As the width and depth increase,
1 https://wiki.dbpedia.org/dbpedia-data-set-2015-04.
Y. Sun et al.
one-hop traversal from b 1 , triple instance [b 1 , [e 5 , a 1 ]] is written into the results
of q 1 . Then, a 1 is obtained and set as an initial vertex on (1), because a 1 is not
included into the key of temp results. Due to RE q1 ∩ iN F T =?A, iE ?A (e 5 ),
triple instance [a 1 , [e 5 , b 1 ]] is written into the results of q 1 , and [a 1 , [e 7 , f 1 ]] is
written into temp results through one-hop traversal from a 1 . Finally, final results
of q 1 are carried out because b 1 has included into results of q 1 .
The processing of obtained results of q 1 , q 2 , and q 3 are similar to q 1 . Through
M-PM algorithm, the results of multiple BGP graphs can be obtained by one
traversal of data graphs.
4 Experimental Evaluation
Query Sets. In the selection of query sets, residual edges of query node are an
important factor. In the D-Tree of query graphs, the residual edges of non-leaf
query node are associated with overlapped query subgraphs. As the depth of
D-tree increases, the closer to root node are and the more times the query node
overlap. Therefore, the multiple query graphs with the same and different depths
are selected into our query sets.
Datasets. A simulated dataset is selected in our experimental analysis. DBpedia 2015A
1 describes the information of sports and sport events. It contains
30,000 RDF triple instances with 20 triple patterns. Due to the small number of
triple patterns, it is different for DBpedia 2015A to reflect the benefits of multipattern matching algorithm. Therefore, a simulated dataset based on DBpedia
2015A is created, which contains almost 3 million RDF triple instances with 300
triple patterns.
Configurations. All experiments were performed on the Intel Xeon 5118 processor with 24GB RAM. The system is equipped with main memory, and it runs
a 64-bit Linux 3.13.0 kernel.
In this experimental analysis, we look at the multi-pattern matching with
same and different depth of D-Tree on simulated dataset.
Basic line (BL for short) algorithm is compared with M-PM algorithm. The
idea of BL algorithm is to reduce the size of original RDF graph by query parent
node and response query child node on reduced RDF graph. However, it does
not avoid the rematching on the overlapped RDF subgraphs between parent
and child node. Assumed that the size of multiple BGP graphs is n and the
quantity of data graphs is m (quantity statistics of triple instance). The time
complexity of BL algorithm is similar to O(n · m). And the time complexity
of M-PM algorithm is approximatively O(m) + O(log
n
m · m). Therefore, M-PM
algorithm is better time-efficient than basic line algorithm.
Figure 4a describes the execution time on different widths of D-Tree with
same depth. Figure 4b depicts the execution time on different depths of D-Tree
with same width. The root query node contains 80 triple patterns, and each child
node has 10 edges more than its parent node. As the width and depth increase,
1 https://wiki.dbpedia.org/dbpedia-data-set-2015-04.