跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.10736 · v1

Tunnels: Compressing the Solution Subgraph of Regular Path Queries

首次提交 2026-11-07 21:46
版本更新 2026-11-07 21:46
雷达观测 2026-11-10 11:14
arXiv ↗PDF ↗

摘要

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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-07 21:46 · 最新观测版本

Tunnels: Compressing the Solution Subgraph of Regular Path Queries

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.

查看此版本解读 →查看此版本原文 ↗