li-distributedsubgraphmatching-2019.pdf (7.04 MB)
Distributed subgraph matching on big knowledge graphs using Pregel
journal contribution
posted on 2019-01-01, 00:00 authored by Qiang Xu, Xin Wang, Jianxin LiJianxin Li, Qingpeng Zhang, Lele ChaiWith 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.
History
Journal
IEEE accessVolume
7Pagination
116453 - 116464Publisher
Institute of Electrical and Electronics EngineersLocation
Piscataway, N.J.Publisher DOI
Link to full text
ISSN
2169-3536Language
EnglishPublication classification
C1 Refereed article in a scholarly journalUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC