S+EPP: 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 analyticsplatforms, and then enhances existing SPARQL engines tosupport summary-based exploration and navigational queryoptimization. The construction component adds a novel op-timization to a parallel bisimulation algorithm implementedon a multi-core graph processing framework. We show thatfor several large, disk resident, real world graphs, full sum-mary construction can be completed in roughly the sametime as the data load. The query translation componentsupports Extended Property Paths (EPPs), an enhance-ment of SPARQL 1.1 property paths that can express asignificantly larger class of navigational queries. EPPs areimplemented via rewritings into a widely used SPARQLsubset. The optimization component can (transparently tousers) translate EPPs defined on instance graphs into EPPsthat take advantage of bisimulation summaries. S+EPPscombines the query and optimization translations to enablesummary-based optimization of graph traversal queries ontop of off-the-shelf SPARQL processors. The demonstra-tion showcases the construction of bisimulation summariesof graphs (ranging from millions to billions of edges), to-gether with the exploration benefits and the navigationalquery speedups obtained by leveraging summaries storedalongside the original datasets.