A Dependency-Extended Method
of Multi-pattern Matching
for RDF Graph
Yunhao Sun
1 , Fengyu Li
1 , Guanyu Li
1(B) , Heng Chen
1,2 , and Wei Jiang
1
1 DaLian Maritime University, Dalian 116026, China
rabitlee@163.com,syh8086@163.com
2 DaLian University of Foreign Languages, Dalian 116044, China
Abstract. The problem of multi-pattern matching for RDF graph is an
extended problem of subgraph isomorphism, where Resource Description
Framework (RDF) is a graph-based data model for information sharing
on Web. In real world, concurrent execution of multi-queries is more realistic than single query. However, the problem about re-computations of
common subgraphs always limits the time efficiency of matching processing. To solve this problem, an algorithm of multi-pattern matching for
RDF graph is proposed, which can response to multiple queries through
one traversal of RDF graph. The experimental results show that our algorithm can avoid the re-computations of common subgraphs and improve
up to 70% of time efficiency than basic line algorithm.
Keywords: RDF graph · Multi-pattern matching · Dependent tree ·
Node fragment table
1 Introduction
Resource Description Framework (RDF) [5] is a graph-based data model that is
the basic model for semantic identification of resources in Semantic Web [4]. The
pattern matching for RDF graph (PM for short) refers to finding all the RDF
subgraphs that are isomorphic to query graphs. The multi-pattern matching for
RDF graphs (M-PM for short) is an extension of PM problem. A core challenge
of M-PM problem is to avoid the re-computations about the matching processing
on common subgraphs of multiple query graphs. To cope with the core challenge,
an algorithm of M-PM problem is proposed in this paper, which can response
the multiple query graphs by one traversal on data graphs.
The most of researches pay more attention on the single-pattern matching processing and multi-patterns matching optimization. For the single-pattern
matching processing, a relational approach is usually used to index and match
RDF graphs. Weiss et al. [1] and Perez et al. [6] employ an index-based solution
by indexing and matching RDF graphs on a B
+ -tree. Srdjan Komazec et al. [7]
c
Springer Nature Singapore Pte Ltd. 2020
Q. Liang et al. (Eds.): Artificial Intelligence in China, LNEE 572, pp. 180–188, 2020.
https://doi.org/10.1007/978-981-15-0187-6_21
of Multi-pattern Matching
for RDF Graph
Yunhao Sun
1 , Fengyu Li
1 , Guanyu Li
1(B) , Heng Chen
1,2 , and Wei Jiang
1
1 DaLian Maritime University, Dalian 116026, China
rabitlee@163.com,syh8086@163.com
2 DaLian University of Foreign Languages, Dalian 116044, China
Abstract. The problem of multi-pattern matching for RDF graph is an
extended problem of subgraph isomorphism, where Resource Description
Framework (RDF) is a graph-based data model for information sharing
on Web. In real world, concurrent execution of multi-queries is more realistic than single query. However, the problem about re-computations of
common subgraphs always limits the time efficiency of matching processing. To solve this problem, an algorithm of multi-pattern matching for
RDF graph is proposed, which can response to multiple queries through
one traversal of RDF graph. The experimental results show that our algorithm can avoid the re-computations of common subgraphs and improve
up to 70% of time efficiency than basic line algorithm.
Keywords: RDF graph · Multi-pattern matching · Dependent tree ·
Node fragment table
1 Introduction
Resource Description Framework (RDF) [5] is a graph-based data model that is
the basic model for semantic identification of resources in Semantic Web [4]. The
pattern matching for RDF graph (PM for short) refers to finding all the RDF
subgraphs that are isomorphic to query graphs. The multi-pattern matching for
RDF graphs (M-PM for short) is an extension of PM problem. A core challenge
of M-PM problem is to avoid the re-computations about the matching processing
on common subgraphs of multiple query graphs. To cope with the core challenge,
an algorithm of M-PM problem is proposed in this paper, which can response
the multiple query graphs by one traversal on data graphs.
The most of researches pay more attention on the single-pattern matching processing and multi-patterns matching optimization. For the single-pattern
matching processing, a relational approach is usually used to index and match
RDF graphs. Weiss et al. [1] and Perez et al. [6] employ an index-based solution
by indexing and matching RDF graphs on a B
+ -tree. Srdjan Komazec et al. [7]
c
Springer Nature Singapore Pte Ltd. 2020
Q. Liang et al. (Eds.): Artificial Intelligence in China, LNEE 572, pp. 180–188, 2020.
https://doi.org/10.1007/978-981-15-0187-6_21