論文の概要: CORGI: Efficient Pattern Matching With Quadratic Guarantees

• arxiv url: http://arxiv.org/abs/2511.13942v1
• Date: Mon, 17 Nov 2025 21:49:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-19 16:23:52.818512
• Title: CORGI: Efficient Pattern Matching With Quadratic Guarantees
• Title（参考訳）: CORGI: クアドラティックな保証者との効果的なパターンマッチング
• Authors: Daniel Weitekamp,
• Abstract要約: 我々は,AIベースのシステムにおいて,CORGIと呼ばれるアルゴリズムがタイトな時間制約で問題を解く方法を示す。 CORGIは、単一の満足度マッチを見つけ、コンフリクトセット全体をメモリにコミットすることなく、メモリにストリームする能力を見出す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Rule-based systems must solve complex matching problems within tight time constraints to be effective in real-time applications, such as planning and reactive control for AI agents, as well as low-latency relational database querying. Pattern-matching systems can encounter issues where exponential time and space are required to find matches for rules with many underconstrained variables, or which produce combinatorial intermediate partial matches (but are otherwise well-constrained). When online AI systems automatically generate rules from example-driven induction or code synthesis, they can easily produce worst-case matching patterns that slow or halt program execution by exceeding available memory. In our own work with cognitive systems that learn from example, we've found that aggressive forms of anti-unification-based generalization can easily produce these circumstances. To make these systems practical without hand-engineering constraints or succumbing to unpredictable failure modes, we introduce a new matching algorithm called CORGI (Collection-Oriented Relational Graph Iteration). Unlike RETE-based approaches, CORGI offers quadratic time and space guarantees for finding single satisficing matches, and the ability to iteratively stream subsequent matches without committing entire conflict sets to memory. CORGI differs from RETE in that it does not have a traditional $β$-memory for collecting partial matches. Instead, CORGI takes a two-step approach: a graph of grounded relations is built/maintained in a forward pass, and an iterator generates matches as needed by working backward through the graph. This approach eliminates the high-latency delays and memory overflows that can result from populating full conflict sets. In a performance evaluation, we demonstrate that CORGI significantly outperforms RETE implementations from SOAR and OPS5 on a simple combinatorial matching task.
• Abstract（参考訳）: ルールベースのシステムは、AIエージェントの計画やリアクティブ制御、低レイテンシリレーショナルデータベースクエリといったリアルタイムアプリケーションで有効なように、厳密な時間制約内で複雑なマッチング問題を解決する必要がある。 パターンマッチングシステムは、多くの制約が満たされていない変数と規則の一致を見つけるために指数時間と空間を必要とする場合や、組合せ中間部分一致を生成する場合(ただし、あまり制約がない場合)に遭遇することがある。 オンラインAIシステムは、サンプル駆動の帰納法やコード合成からルールを自動生成するので、利用可能なメモリを超過してプログラムの実行を遅くまたは停止する最悪のケースマッチングパターンを簡単に生成できる。 例えば、我々の認知システムを用いた研究で、攻撃的なアンチユニフィケーションに基づく一般化がこれらの状況を容易に生み出せることがわかりました。 手作業による制約や予測不能な障害モードに対処することなく,これらのシステムを実用的なものにするために,CORGI (Collection-Oriented Relational Graph Iteration) と呼ばれる新しいマッチングアルゴリズムを導入する。 RETEベースのアプローチとは異なり、CORGIは、単一満足なマッチを見つけるための2次時間と空間保証を提供し、コンフリクトセット全体をメモリにコミットすることなく、後続のマッチを反復的にストリーミングする機能を提供する。 CORGIはRETEと異なり、部分一致を収集するための従来の$β$-Memoryを持っていない。 その代わり、CORGIは2段階のアプローチを取る: 接地関係のグラフはフォワードパスで構築・維持され、イテレータはグラフを遡って作業することで必要に応じて一致を生成する。 このアプローチは、完全なコンフリクトセットを発生させる可能性のある、レイテンシの遅延とメモリオーバーフローを排除します。 性能評価において、CORGIは単純な組合せマッチングタスクにおいて、SOARとOPS5からRETE実装を著しく上回っていることを示す。

関連論文リスト

• G-CSEA: A Graph-Based Conflict Set Extraction Algorithm for Identifying Infeasibility in Pseudo-Boolean Models [0.5773629510985792]
  一般的な診断手法は、未認識不実現サブセット(IIS)の計算である。 二変数上の不等式関係を持つ擬似ブール制約を用いて定式化されたモデルを考える。 提案手法は制約伝搬中に含意グラフを構築し,コンフリクトを検出すると,両決定枝にまたがるすべての制約をトレースする。
  論文  参考訳（メタデータ） (2025-09-16T16:09:30Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAGは、質問駆動セマンティックグラフ分割と協調サブグラフ検索による制限に対処するマルチエージェントRAGフレームワークである。 革新的なフレームワークは、まずリンク情報のセマンティック分割を作成し、次にタイプ特化知識ベースを使用してマルチエージェントRAGを実現する。 属性対応グラフセグメンテーションは、知識グラフを意味的に一貫性のあるサブグラフに分割し、サブグラフが異なるクエリタイプと整合することを保証する。 階層的なマージモジュールは、論理的検証を通じて、部分グラフ由来の解答間の矛盾を解消する。
  論文  参考訳（メタデータ） (2025-05-20T06:44:34Z)
• COrAL: Order-Agnostic Language Modeling for Efficient Iterative Refinement [80.18490952057125]
  反復改良は、複雑なタスクにおける大規模言語モデル(LLM)の能力を高める効果的なパラダイムとして登場した。 我々はこれらの課題を克服するために、コンテキストワイズ順序非依存言語モデリング(COrAL)を提案する。 当社のアプローチでは、管理可能なコンテキストウィンドウ内で複数のトークン依存関係をモデル化しています。
  論文  参考訳（メタデータ） (2024-10-12T23:56:19Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQは、マルチタスク学習問題とエンティティペアの分布を回避する、シーングラフ生成の新しい定式化である。 我々は,DETRをベースとしたエンコーダ-デコーダ条件付きクエリを用いて,エンティティラベル空間を大幅に削減する。 実験結果から、TraCQは既存のシングルステージシーングラフ生成法よりも優れており、Visual Genomeデータセットの最先端の2段階メソッドを多く上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-06-09T06:02:01Z)
• HyRSM++: Hybrid Relation Guided Temporal Set Matching for Few-shot Action Recognition [51.2715005161475]
  そこで本研究では,数発のアクション認識のための時間的マッチング手法として,ハイブリッドリレーションド・テンポラル・セット・マッチングを提案する。 HyRSM++の中核となる考え方は、すべてのビデオをタスクに統合して差別的な表現を学ぶことである。 提案手法は,様々な撮影条件下での最先端性能を実現する。
  論文  参考訳（メタデータ） (2023-01-09T13:32:50Z)
• Towards Correlated Sequential Rules [4.743965372344134]
  高実用性シーケンシャルルールマイニング(HUSRM)は、結果のシーケンシャルパターンの発生を予測できる信頼度や確率を調査するために設計された。 HUSRMと呼ばれる既存のアルゴリズムは、生成されたシーケンシャルルール間の相関を無視しながら、すべての許容ルールを抽出することに制限されている。 本稿では,HUSRMに相関の概念を統合するために,CoUSR(Cocorlation High-utility Sequence Rule Minr)と呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-27T17:27:23Z)
• Pipelined correlated minimum weight perfect matching of the surface code [56.01788646782563]
  最小ウェイト完全マッチングを用いて表面コードを復号するパイプライン手法について述べる。 独立な非通信可能な並列化処理段階は、潜在的な相関に従ってグラフを再重み付けする。 後続の一般的なステージがマッチングを終了します。 完全にフォールトトレラントなトーリック, 回転しない, 回転する曲面符号に対して, 新たなアルゴリズムの有効性を検証した。
  論文  参考訳（メタデータ） (2022-05-19T19:58:02Z)
• Towards Dynamic Consistency Checking in Goal-directed Predicate Answer Set Programming [2.3204178451683264]
  本稿では,動的一貫性チェック(Dynamic Consistency check)と呼ばれるトップダウン評価戦略のバリエーションを示す。 これにより、リテラルがプログラムのグローバルな制約に関連する否定と互換性がないかどうかを判断できる。 我々は、標準バージョンのs(CASP)の最大90倍のスピードアップを実験的に観察した。
  論文  参考訳（メタデータ） (2021-10-22T20:38:48Z)
• Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm [20.582965700659788]
  我々は、最も単純なアルゴリズムであるGREEDYの競合比を、関連する離散過程を連続的に近似することによって推定する。 驚くべきことに、GREEDYは、オンラインマッチングのためのもう1つの有名なアルゴリズムであるRANKINGよりも優れたパフォーマンスを保証することができる。
  論文  参考訳（メタデータ） (2021-07-02T12:18:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。