关键词: RDF图, 多模式匹配, 依赖树, 节点分片表

Abstract:

The problem of multi-pattern matching is an extension of pattern matching, whose main challenge is the concurrent execution strategy among multiple query graphs. To solve this challenge, a Multi-Pattern Matching（M-PM） method for RDF graph is proposed. Firstly, a Dependency Tree（D-Tree） is constructed based on the inclusion relations of multiple query graphs and maximum public query subgraphs. Secondly, a Node Fragmentation Table（NFT） is proposed to extend the single inclusion relation of D-Tree. Finally, a speed up algorithm of multi-pattern matching is designed, which can obtain the results of multiple query graphs by one-off traversal of data graph. The experimental results show that M-PM method can improve the matching time-efficiency of more 70% than general method. With the fixed scales of query graphs, matching time-efficiency is consistent with the quantity of residual edges, where the more the residual edges are and the higher the time-efficiency is.

Key words: RDF graph, Multi-Pattern Matching（M-PM）, Dependency Tree（D-Tree）, Node Fragmentation Table（NFT）