P3RPQ: Pregel-Based Parallel Provenance-Aware Regular Path Query Processing on Large RDF Graphs

Yueqi Xin, Bingyi Zhang, Xin Wang, Qiang Xu, Zhiyong Feng

Abstract

This paper proposes a novel method for answering Pregel-based Parallel Provenance-aware Regular Path Queries (P3RPQ) on large RDF graphs. Our method is developed using the Pregel framework, which utilizes Glushkov automata to keep track of the matching process of RPQs in parallel. Meanwhile, four optimization strategies are devised, which can reduce the response time of the basic algorithm dramatically and overcome the counting paths problem to some extent. The experiments are conducted to verify the performance of our algorithms on both synthetic and real-world datasets.
BibTeX
@inproceedings{xin2018p,
  author = {Yueqi Xin and Bingyi Zhang and Xin Wang and Qiang Xu and Zhiyong Feng},
  title = {{P3RPQ: Pregel-Based Parallel Provenance-Aware Regular Path Query Processing on Large RDF Graphs}},
  booktitle = {The Web Conference},
  year = {2018},
  doi = {10.1145/3184558.3186908},
}

Loading related content...

Figure