H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs
H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs
This paper introduces H-BRICK, a method for efficient reachability queries on directed grid graphs. By partitioning the graph into tiles and computing local Boolean Kleene closures, H-BRICK projects summaries onto tile boundaries and composes them recursively. The authors prove the construction is exact within Boolean Kleene algebra. Experiments show that H-BRICK outperforms directed search and component-based baselines in storage efficiency and throughput, achieving up to 22.9x speedup in batched queries compared to scalar loops.
The authors present H-BRICK, a hierarchical indexing method for directed grid graphs that achieves exact reachability queries with significantly reduced storage compared to full transitive closure, demonstrating throughput improvements of up to 22.9x in batched evaluations on specific query loads.
Source: arXiv Robotics — research abstracts · Read original article ↗
Loading article text…
What the source reports
Publisher-reported claims, with original evidence. These results have not been independently verified by RoboSignal.
Reported numbers
throughput improvement
5
View original evidence
ng endpoint lifts across many-source/many-target queries amortizes hierarchical traversal and, at k=64, yields a 5.0x-22.9x throughput improvement over the scalar query loop. The results show that hierarchical boundary compression is most advantageous in query-intensive spatial graphs where online search traverses large reachable regions and the hierarchy maintains compact boundary interfaces.
Open source S5throughput improvement
22.9
View original evidence
ng endpoint lifts across many-source/many-target queries amortizes hierarchical traversal and, at k=64, yields a 5.0x-22.9x throughput improvement over the scalar query loop. The results show that hierarchical boundary compression is most advantageous in query-intensive spatial graphs where online search traverses large reachable regions and the hierarchy maintains compact boundary interfaces.
Open source S5query count
64
View original evidence
ng endpoint lifts across many-source/many-target queries amortizes hierarchical traversal and, at k=64, yields a 5.0x-22.9x throughput improvement over the scalar query loop. The results show that hierarchical boundary compression is most advantageous in query-intensive spatial graphs where online search traverses large reachable regions and the hierarchy maintains compact boundary interfaces.
Open source S5
- paper: not_reported
Source excerpts and review record
Automatically extracted; no manual editorial approval recorded.
ng endpoint lifts across many-source/many-target queries amortizes hierarchical traversal and, at k=64, yields a 5.0x-22.9x throughput improvement over the scalar query loop. The results show that hierarchical boundary compression is most advantageous in query-intensive spatial graphs where online search traverses large reachable regions and the hierarchy maintains compact boundary interfaces.
Open source S5
the boundary projection of the regional reflexive transitive closure, and every cell-to-cell query agrees with reachability in the original graph. Experiments on directed grid graphs across diverse map topologies compare H-BRICK against directed search and component-based baselines, and compare its storage requirements against full transitive closure. A batched reachability evaluation further demonstrates that shari
Open source S4
Source：arXiv Robotics — research abstracts · arxiv.org