Distributed Subgraph Matching on Big Knowledge Graphs Using Pregel

IEEE Access

Xin Wang¹  Qiang Xu¹  Lele Chai¹  Qingpeng Zhang²  Jianxin Li³ 

[1] College of Intelligence and Computing, Tianjin University, Tianjin, China;School of Data Science, City University of Hong Kong, Hong Kong;School of Information Technology, Deakin University, Burwood, VIC, Australia;

关键词: Subgraph matching;    distributed;    knowledge graphs;    RDF;    Pregel;   

DOI  :  10.1109/ACCESS.2019.2936465

来源: DOAJ

【 摘 要 】

With RDF becoming the de facto standard 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 method SP-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 our SP-Tree subgraph matching method outperforms the state-of-the-art methods by an order of magnitude.

【 授权许可】

Unknown