Regular path query results compressed drastically with tunnels technique

Tunnels: Compressing the Solution Subgraph of Regular Path Queries

Data Structures and Algorithms

Summary

Some database questions ask for all paths that match a certain pattern, which can be extremely many or even infinite. The authors explore a way to shrink the data that describes all these paths, called the solution subgraph, by storing just parts needed and rebuilding the rest when needed through small reruns called tunnels. This method reduces the storage size a lot, by hundreds or thousands of times, while keeping the time to get answers reasonable. They test this on several kinds of queries and show it works well across different cases.

What this means in practice

  • For graph database engineers: Store and transmit large sets of regular path query results more compactly while enabling on-demand reconstruction to save space.
  • For network analysis teams: Reduce memory use when exploring complex reachability queries on network graphs by compressing intermediate traversal data.

Authors

Adrián Gómez-Brandón, Gonzalo Navarro

Abstract

Regular path queries (RPQs) are increasingly expected to return the paths that match them, not only their endpoints. Since the number of matching paths can be exponential or infinite, a standard way to deliver them (PMR) is the subgraph $\Hs$ of the product between the graph and the query automaton that contains exactly the nodes lying on some solution path. We show that $\Hs$ can be compressed much further when the graph is available to the decoder: most of $\Hs$ can be regenerated by re-running small parts of the traversal, and only the places where the traversal would waste significant effort on dead branches need to be stored. We formalize this as \emph{tunnels}: regions of $\Hs$ that are re-expanded from a stored entry point with a bounded amount of extra work, either an absolute budget or one proportional to the output produced. We handle the three classes of RPQs: constant-to-variable, constant-to-constant, and variable-to-variable. In the latter, we study the combination of tunnels with cutting the query at a selective articulation point of the automaton and encoding the answer as a union of Cartesian products of leftward and rightward traversals. Our experimental results show improvements of 2 to 3 orders of magnitude over the baseline space of PMR, for an acceptable increase in traversal time.