Powerful and efficient bulk shortest-path queries: Cypher language extension & Giraph implementation

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.