Distributed Subgraph Matching on Big Knowledge Graphs Using Pregel
Qiang Xu, Xin Wang, Jianxin Li, Qingpeng Zhang, Lele Chai · IEEE Access · 2019
With RDF becoming thede factostandard for representing knowledge graphs, it is indispensable to develop scalable subgraph matching algorithms over big RDF graphs stored in distributed clusters. In this paper, we propose a novel distributed subgraph matching methodSP-Tree, using the Pregel model, to answer subgraph matching queries on big RDF graphs. In our method, the query graph is transformed to a variant spanning tree based on the shortest paths. Two optimization techniques are proposed to improve the efficiency of our algorithms. One employs RDF shapes to filter out local computations and messages passed, the other postpones the Cartesian product operations in the matching process to reduce intermediate results. The extensive experiments on both synthetic and real-world datasets show that ourSP-Treesubgraph matching method outperforms the state-of-the-art methods by an order of magnitude.