論文の概要: H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs
- arxiv url: http://arxiv.org/abs/2611.08119v1
- Date: Thu, 05 Nov 2026 14:53:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 04:55:13.549907
- Title: H-BRICK: Hierarchical Boundary Reachability Index with Compressed Kleene Closure for Directed Grid Graphs
- Title（参考訳）: H-BRICK:方向格子グラフに対する圧縮クレーンクロージャ付き階層境界到達率指数
- Abstract要約: H-BRICKは階層的境界到達性指数であり、有向格子グラフ上のセル間正確なクエリに対する圧縮クレーン閉包である。
H-BRICKは,オンライン検索が大きな到達可能な領域を横断するクエリ集約空間グラフにおいて,最も有利であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Repeated directed reachability queries arise in online path planning, task-agent allocation, and swarm control on static grid maps, where reachability is asymmetric and full transitive closure is storage-prohibitive. We introduce H-BRICK, a Hierarchical Boundary Reachability Index with Compressed Kleene closure for exact cell-to-cell queries on directed grid graphs. H-BRICK partitions the graph into tiles, computes a local Boolean Kleene closure within each tile, and projects it onto the tile's boundary ports. The resulting directed port-to-port summaries are then composed recursively across shared interfaces up to a single root covering the graph. We prove algebraically that the construction is exact: in the Boolean Kleene algebra of binary relations, every composed summary equals 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 sharing 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.
- Abstract（参考訳）: オンラインパス計画、タスクエージェント割り当て、静的グリッドマップ上のスワム制御において、到達性は非対称であり、完全な推移的クロージャはストレージ禁止である。
有向格子グラフ上のセル間正確なクエリに対して,圧縮クリーネ閉包付き階層境界到達性指数であるH-BRICKを導入する。
H-BRICKはグラフをタイルに分割し、各タイル内の局所的なブールクレーン閉包を計算し、タイルの境界ポートに投影する。
結果として得られたポート・ツー・ポートの要約は、グラフをカバーする1つのルートまで、共有インターフェース間で再帰的に構成される。
二項関係のブール・クリーネ代数において、すべての合成要約は局所回帰的推移的閉包の境界射影と等しく、全てのセル・セル間の問い合わせは元のグラフの到達可能性に一致する。
様々な地図トポロジにまたがる有向グリッドグラフの実験は、H-BRICKを有向探索とコンポーネントベースラインと比較し、そのストレージ要求を全推移閉包と比較する。
バッチ化到達性評価により、多くのソース/マルチターゲットクエリ間での共有エンドポイントリフトが階層的トラバースを補正し、k=64ではスカラークエリループよりも5.0x-22.9倍のスループット向上が得られることが示された。
その結果、階層境界圧縮は、オンライン検索が大きな到達可能な領域を横切り、階層がコンパクトな境界インターフェースを維持するようなクエリ集約空間グラフにおいて最も有利であることが示された。
関連論文リスト
- Corpus-Guided Dual-Path Propagation for Graph Retrieval-Augmented Generation [7.639781363951024]
関係のないTri-Graphを強化するために,NexusRAGと呼ばれるシンプルで効果的な手法を提案する。
3つのマルチホップQAベンチマークとGraphRAG-Benchのドメイン固有のサブセットの実験は、NexusRAGが既存のアプローチを一貫して上回っていることを示している。
論文 参考訳（メタデータ） (2026-09-29T14:20:46Z) - Unifying Graph Neural Networks Through a Common Layer Equation [75.88127999406392]
7つのコンポーネントを通して被覆されたアーキテクチャを表現する共通層方程式を導入する。
中央の因子化は、伝達銀行によってエンコードされた情報と、メッセージマップによってエンコードされた動きとを分離する。
この統合を明確化し、標準層とコンポーネント割り当ての作業的削減を通じて、チェック可能にする。
論文 参考訳（メタデータ） (2026-08-17T04:37:59Z) - Unified Dominance Graph for Interval-Predicate Approximate Nearest Neighbor Search [8.875776605139185]
我々は、オブジェクト間隔とクエリ間隔の間の述語によって妥当性が決定されるInterval-Predicate ANNSについて検討する。
既存のレンジフィルタANNS法は1次元スカラーフィルタのために設計されている。
We propose the Unified Dominance Graph (UDG) a graph-indexing framework for the closed two-bound conjunctive fragment of IPANNS。
論文 参考訳（メタデータ） (2026-06-23T06:46:28Z) - Beyond Chunk-Local Extraction: Cross-Chunk Graph Augmentation for GraphRAG [11.699085890492833]
GraphRAGは、コーパスを明示的な知識グラフとして整理することで、検索拡張生成を拡張する。
既存のフレームワークは個々のチャンク内のエンティティとリレーションを抽出し、クロスチャンクの関係はインデックスから体系的に欠落している。
GNN誘導のCROSS-Chunk Graph AUGmentation法であるCrossAugを提案する。
論文 参考訳（メタデータ） (2026-05-27T05:55:53Z) - SliceGraph: Mapping Process Isomers in Multi-Run Chain-of-Thought Reasoning [60.650808962786364]
我々は、CoTスライス間の疎活性化キージャカード類似性に対して、相互kNNによって構築された問題モデル-セルグラフであるSliceGraphを提案する。
同じ正規化された回答を共有する正しいCoTは、複数のプロセスファミリに分割されていることを示す。
また、プロセスファミリは、一致したnull制御の下で異なる遷移カーネルで同じアトラスをナビゲートすることを示す。
論文 参考訳（メタデータ） (2026-05-14T09:37:26Z) - Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees [10.806910118253976]
グラフベースのRetrieval-Augmented Generation (RAG)システムは複雑な関係を捉えるために相互接続された知識構造を利用する。
本稿では,各クエリの全体的意味論にグラフトラバーサルを動的に適用する学習自由フレームワークであるQuery-Aware Flow Diffusion RAG (QAFD-RAG)を提案する。
QAFD-RAGは、弱い信号対雑音条件下で、高い確率で関連部分グラフを復元する。
論文 参考訳（メタデータ） (2026-04-21T08:53:34Z) - CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data [11.878755010092922]
CubeGraphは任意の空間制約でベクトル探索を統合するように設計されたフレームワークである。
クエリ実行中、CubeGraphは、空間セルがクエリフィルタと交差するたびに、隣接する立方体レベルのインデックスをフライで縫合する。
論文 参考訳（メタデータ） (2026-04-08T02:49:55Z) - SAGE: Structure Aware Graph Expansion for Retrieval of Heterogeneous Data [47.930782177987446]
不均一なコーパスに答える検索拡張された質問は、テキスト、テーブル、グラフノード間で接続されたエビデンスを必要とする。
標準レトリバーリーダーパイプラインは、独立にチャンクされたテキスト上の平坦な類似性検索を使用し、モダリティ間のマルチホップエビデンスチェーンを欠いている。
SAGE(Structure Aware Graph Expansion)フレームワークを提案する。これは、パーセンタイルベースのプルーニングとメタデータ駆動の類似性を利用して、チャンクレベルのグラフをオフラインで構築する。
暗黙的クロスモーダルコーパスと明示的スキーマグラフのエージェント検索であるSPARK(Structure Aware Planning Agent for Retrieval over Knowledge Graphs)のハイブリッド高密度スパース検索を用いて初期検索をインスタンス化する。
論文 参考訳（メタデータ） (2026-02-18T23:57:19Z) - Higher-order Clustering and Pooling for Graph Neural Networks [77.47617360812023]
グラフニューラルネットワークは、多数のグラフ分類タスクにおいて最先端のパフォーマンスを達成する。
HoscPoolはクラスタリングベースのグラフプーリング演算子で、階層的に高階情報をキャプチャする。
グラフ分類タスクにおいてHoscPoolを評価し,そのクラスタリングコンポーネントを地層構造を持つグラフ上で評価する。
論文 参考訳（メタデータ） (2022-09-02T09:17:10Z) - Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
グラフクエリ拡張(GQE)が提示され、教師付き方法で学習され、クエリの拡張近傍で集約を実行する。
この技術は既知のベンチマークよりも最先端の結果が得られる。
論文 参考訳（メタデータ） (2021-12-05T19:48:42Z) - Relational Message Passing for Knowledge Graph Completion [78.47976646383222]
本稿では,知識グラフ補完のためのリレーショナルメッセージパッシング手法を提案する。
エッジ間でリレーショナルメッセージを反復的に送信し、近隣情報を集約する。
その結果,本手法は最先端の知識完成手法よりも大きなマージンで優れていることがわかった。
論文 参考訳（メタデータ） (2020-02-17T03:33:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。