Powerful and efficient bulk shortest-path queries: Cypher language extension & Giraph implementation
Proceedings of the VLDB Endowment , Volume 9 - Issue 12
Shortest-path computation is central to many graph queries. However, current graph-processing platforms tend to offer limited solutions, typically supporting only single-source and all-pairs shortest path algorithms, with poor filtering options. In this paper we address the shortest-path computation problem in two complementary directions. First, we introduce a restrictable, top-N "bulk" shortest-weighted-paths operator in the Cypher graph query language, that subsumes all previously known shortest path variants. In addition to ease of use, both in terms of short notation and more robust performance thanks to guaranteed amenability to pruning, this operator supports calculated path weights, as well as filtering on the path edges and vertices. Second, we provide a scalable algorithm for the parallel implementation of this top-N operator on Giraph, a graph-processing system based on the Bulk Synchronous Parallel (BSP) model. We present an initial evaluation on a number of queries executed over the LDBC-SNB dataset.
|Proceedings of the VLDB Endowment|
Rutgers, P, Martella, C, Voulgaris, S, & Boncz, P.A. (2016). Powerful and efficient bulk shortest-path queries: Cypher language extension & Giraph implementation. Proceedings of the VLDB Endowment, 9(12). doi:10.1145/1235