li-efficientsubgraph-2019.pdf (1.53 MB)
Efficient subgraph matching on large RDF graphs using MapReduce
journal contribution
posted on 2019-03-01, 00:00 authored by X Wang, L Chai, Q Xu, Y Yang, Jianxin LiJianxin Li, J Wang, Y ChaiWith the popularity of knowledge graphs growing rapidly, large amounts of RDF graphs have been released, which raises the need for addressing the challenge of distributed subgraph matching queries. In this paper, we propose an efficient distributed method to answer subgraph matching queries on big RDF graphs using MapReduce. In our method, query graphs are decomposed into a set of stars that utilize the semantic and structural information embedded RDF graphs as heuristics. Two optimization techniques are proposed to further improve the efficiency of our algorithms. One algorithm, called RDF property filtering, filters out invalid input data to reduce intermediate results; the other is to improve the query performance by postponing the Cartesian product operations. The extensive experiments on both synthetic and real-world datasets show that our method outperforms the close competitors S2X and SHARD by an order of magnitude on average.
History
Journal
Data science and engineeringVolume
4Issue
1Pagination
24 - 43Publisher
SpringerLocation
[Berlin, Germany]Publisher DOI
Link to full text
ISSN
2364-1185eISSN
2364-1541Language
engPublication classification
C1 Refereed article in a scholarly journalCopyright notice
2019, The Author(s)Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC