S+EPPs: Construct and Explore Bisimulation Summaries, Plus Optimize Navigational Queries; All on Existing SPARQL Systems

We demonstrate S+EPPs, a system that provides fast con- struction of bisimulation summaries using graph analytics platforms, and then enhances existing SPARQL engines to support summary-based exploration and navigational query optimization. The construction component adds a novel op- timization to a parallel bisimulation algorithm implemented on a multi-core graph processing framework. We show that for several large, disk resident, real world graphs, full sum- mary construction can be completed in roughly the same time as the data load. The query translation component supports Extended Property Paths (EPPs), an enhance- ment of SPARQL 1.1 property paths that can express a significantly larger class of navigational queries. EPPs are implemented via rewritings into a widely used SPARQL subset. The optimization component can (transparently to users) translate EPPs defined on instance graphs into EPPs that take advantage of bisimulation summaries. S+EPPs combines the query and optimization translations to enable summary-based optimization of graph traversal queries on top of off-the-shelf SPARQL processors. The demonstra- tion showcases the construction of bisimulation summaries of graphs (ranging from millions to billions of edges), to- gether with the exploration benefits and the navigational query speedups obtained by leveraging summaries stored alongside the original datasets.