論文の概要: Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval

• arxiv url: http://arxiv.org/abs/2601.18747v1
• Date: Mon, 26 Jan 2026 18:07:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-27 15:23:09.002837
• Title: Capturing P: On the Expressive Power and Efficient Evaluation of Boolean Retrieval
• Title（参考訳）: Pを捕捉する : ブール検索の表現力と効率的な評価について
• Authors: Amir Aavani,
• Abstract要約: 現代の情報検索は、単純な文書フィルタリングから複雑でニューロシンボリックな推論へと移行しつつある。 我々は、DAG(Directed Acyclic Graphs)に基づく形式的検索言語(mathcalL_R$)を提示し、複雑性クラスを$mathbfP$で取得することを証明する。 この研究は、インデックスを汎用計算エンジンに変換する理論的基礎を確立する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modern information retrieval is transitioning from simple document filtering to complex, neuro-symbolic reasoning workflows. However, current retrieval architectures face a fundamental efficiency dilemma when handling the rigorous logical and arithmetic constraints required by this new paradigm. Standard iterator-based engines (Document-at-a-Time) do not natively support complex, nested logic graphs; forcing them to execute such queries typically results in intractable runtime performance. Conversely, naive recursive approaches (Term-at-a-Time), while capable of supporting these structures, suffer from prohibitive memory consumption when enforcing broad logical exclusions. In this paper, we propose that a retrieval engine must be capable of ``Capturing $\mathbf{P}$'' -- evaluating any polynomial-time property directly over its index in a computationally efficient manner. We define a formal Retrieval Language ($\mathcal{L}_R$) based on Directed Acyclic Graphs (DAGs) and prove it precisely captures the complexity class $\mathbf{P}$. We introduce \texttt{ComputePN}, a novel evaluation algorithm that makes $\mathcal{L}_R$ tractable. By combining native DAG traversal with a memory-efficient ``Positive-Negative'' response mechanism, \texttt{ComputePN} ensures the efficient evaluation of any query in $\mathcal{L}_R$. This work establishes the theoretical foundation for turning the search index into a general-purpose computational engine.
• Abstract（参考訳）: 現代の情報検索は、単純な文書フィルタリングから複雑でニューロシンボリックな推論ワークフローへと移行しつつある。 しかし、この新たなパラダイムで必要とされる厳密な論理的および算術的制約を扱う場合、現在の検索アーキテクチャは基本的な効率のジレンマに直面している。 標準イテレータベースのエンジン(Document-at-a-Time)は、複雑なネスト論理グラフをネイティブにサポートしていない。 逆に、単純な再帰的アプローチ(Term-at-a-Time)は、これらの構造をサポートすることができるが、広い論理的排除を強制する場合は、メモリ消費が禁止される。 本稿では, 計算効率のよい計算手法で, 多項式時間特性を直接評価するために, 検索エンジンが ``Capturing $\mathbf{P}$''' を適用できなければならないことを提案する。 我々は、DAG (Directed Acyclic Graphs) に基づいた形式的検索言語($\mathcal{L}_R$)を定義し、複雑性クラス $\mathbf{P}$ を正確にキャプチャすることを示す。 本稿では,$\mathcal{L}_R$ tractable を実現する新しい評価アルゴリズムである \textt{ComputePN} を紹介する。 ネイティブDAGトラバーサルとメモリ効率の ``Positive-Negative'' 応答メカニズムを組み合わせることで、 \texttt{ComputePN} は $\mathcal{L}_R$ のクエリを効率的に評価する。 この研究は、検索インデックスを汎用計算エンジンに変換する理論的基礎を確立する。

関連論文リスト

• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
  論文  参考訳（メタデータ） (2025-10-09T09:47:40Z)
• You Don't Need Pre-built Graphs for RAG: Retrieval Augmented Generation with Adaptive Reasoning Structures [16.867592142212203]
  大型言語モデル(LLM)はしばしば幻覚に悩まされ、知識を超えた質問を処理する際に、事実的に誤った文を生成する。 Retrieval-augmented Generation (RAG)は、LLM推論をサポートするために、知識ベースからクエリ関連コンテキストを取得することで、この問題に対処する。 既存のGraphベースのRAGメソッドは、コーパスをグラフに変換するためのコストの高いプロセスに依存しており、圧倒的なトークンコストとアップデートのレイテンシを導入している。 本稿では,推論時に推論構造を動的に抽出し,事前に構築したグラフを使わずに適応検索を誘導するLogicRAGを提案する。
  論文  参考訳（メタデータ） (2025-08-08T08:07:40Z)
• Neuro-Symbolic Query Compiler [57.78201019000895]
  本稿では,このギャップを埋めるために,言語文法規則とコンパイラ設計に触発されたニューラルシンボリックなフレームワークQCompilerを提案する。 理論上は、複雑なクエリを形式化するのに最小でも十分なバックス・ナウアー形式(BNF)の文法を$G[q]$で設計する。 葉のサブクエリの原子性は、より正確な文書検索と応答生成を保証し、複雑なクエリに対処するRAGシステムの能力を大幅に改善する。
  論文  参考訳（メタデータ） (2025-05-17T09:36:03Z)
• Enhancing Retrieval Systems with Inference-Time Logical Reasoning [9.526027847179677]
  本稿では,論理的推論を検索プロセスに明示的に組み込む新しい推論時間論理的推論フレームワークを提案する。 提案手法は,自然言語クエリから論理的推論構造を抽出し,個々のコサイン類似度スコアを合成して最終文書スコアを定式化する。
  論文  参考訳（メタデータ） (2025-03-22T20:40:18Z)
• Role Similarity Metric Based on Spanning Rooted Forest [25.35704965777052]
  既存の役割類似度メトリクスは、高時間と空間コストのため、大規模な現実世界ネットワーク上のトップkクエリを処理できない。 textsfForestSimは許容される役割類似度尺度であり、対応するトップk類似度探索アルゴリズムを考案する。 その結果,textsfForestSimは100万規模のネットワーク上で効率的に動作し,最先端の手法に匹敵する性能を発揮することがわかった。
  論文  参考訳（メタデータ） (2021-10-15T05:50:10Z)
• An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
  投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。 本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
  論文  参考訳（メタデータ） (2021-06-08T23:38:29Z)
• Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
  本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。 計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
  論文  参考訳（メタデータ） (2020-05-05T12:10:21Z)

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

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