有向グリッドグラフのための圧縮Kleene閉包を用いた階層的境界到達可能性インデックス

- 静的な directed grid graph 上での cell-to-cell 到達可能性クエリを厳密に答える索引 H-BRICK を提案する研究。 - グラフを tile に分割し、各 tile 内の local Boolean Kleene closure を境界 port に射影した要約を、共有 interface を介して root まで再帰的に合成する階層構造。 - 対象は online path planning、task-agent allocation、swarm control など、到達可能性が非対称で full transitive closure がストレージ的に非現実的な場面。

- 比較対象は directed search と component-based baselines、および full transitive closure のストレージ。 - full transitive closure を保持せずに厳密な到達可能性を答える点が特徴で、階層的な boundary compression によりストレージを抑える。 - 多数 source/target の batched 評価では endpoint lift の共有により階層走査を償却し、k=64 で scalar query loop 比 5.0x–22.9x の throughput 改善。 - どの程度優位かは map topology 依存で、query-intensive な空間グラフで最も有利と報告。

- グラフを tile に分割し、各 tile で local Boolean Kleene closure を計算して境界 port へ射影する。 - 得られた directed port-to-port summary を共有 interface 上で再帰的に合成し、グラフ全体を覆う単一 root まで階層化する。 - Boolean Kleene algebra of binary relations において、合成された各 summary が regional reflexive transitive closure の boundary projection と一致し、cell-to-cell クエリが元グラフの到達可能性と一致することを代数的に証明。 - batched 評価では many-source/many-target クエリ間で endpoint lift を共有し、階層走査を償却する。

- 多様な map topology の directed grid graph 上で、directed search および component-based baselines と比較する実験を実施。 - ストレージ要件を full transitive closure と比較。 - batched reachability evaluation により、k=64 で scalar query loop に対し 5.0x–22.9x の throughput 改善を示す。 - 構成の厳密性は Boolean Kleene algebra 上の代数的証明で示す。

- 階層的 boundary compression は、online search が大きな到達可能領域を走査し、階層がコンパクトな boundary interface を維持できる query-intensive な空間グラフで最も有利。 - 利点は map topology に依存すると示唆される。 - ストレージとクエリ性能の trade-off や、不利になる条件の詳細は要旨からは不明。

- 要旨で直接参照・比較されている directed search および component-based baselines の関連研究。 - full transitive closure を用いる到達可能性索引の研究。 - Boolean Kleene algebra of binary relations や reflexive transitive closure に関する理論研究。 - 階層分割に基づく reachability index（同分野の定番手法として graph partitioning ベースの索引）。