Subgraph Querying with Parallel Use of Query Rewritings and Alternative Algorithms

Abstract

Subgraph queries are central to graph analytics and graph
\nDBs. We analyze this problem and present key novel discoveries and observations on the nature of the problem which
\nhold across query sizes, datasets, and top-performing algorithms. Firstly, we show that algorithms (for both the decision and matching versions of the problem) suffer from
\nstraggler queries, which dominate query workload times. As
\nrelated research caps query times not reporting results for
\nqueries exceeding the cap, this can lead to erroneous conclusions of the methods' relative performance. Secondly, we
\nstudy and show the dramatic effect that isomorphic graph
\nqueries can have on query times. Thirdly, we show that
\nfor each query, isomorphic queries based on proposed query
\nrewritings can introduce large performance benefits. Fourthly,
\nthat straggler queries are largely algorithm-specific: many
\nchallenging queries to one algorithm can be executed efficiently by another. Finally, the above discoveries naturally
\nlead to the derivation of a novel framework for subgraph
\nquery processing. The central idea is to employ parallelism
\nin a novel way, whereby parallel matching/decision attempts
\nare initiated, each using a query rewriting and/or an alternate algorithm. The framework is shown to be highly beneficial across algorithms and datasets.