論文の概要: Efficiency of Query Evaluation Under Guarded TGDs: The Unbounded Arity Case

• arxiv url: http://arxiv.org/abs/2101.11727v1
• Date: Wed, 27 Jan 2021 22:32:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-01 19:12:51.438396
• Title: Efficiency of Query Evaluation Under Guarded TGDs: The Unbounded Arity Case
• Title（参考訳）: ガード付きTGDにおけるクエリ評価の効率性:非有界アリティケース
• Authors: Cristina Feier
• Abstract要約: 本稿では、ガード付きTGD(GTGD)と接続型クエリ(UCQ)に基づいて、オントロジー媒介クエリ(OMQ)を評価する際のパラメータ化複雑性を分析する。
• 参考スコア（独自算出の注目度）: 1.370633147306388
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The paper analyzes the parameterized complexity of evaluating Ontology Mediated Queries (OMQs) based on Guarded TGDs (GTGDs) and Unions of Conjunctive Queries (UCQs), in the setting where relational symbols might have unbounded arity and where the parameter is the size of the OMQ. It establishes exact criteria for fixed-parameter tractability (fpt) evaluation of recursively enumerable classes of such OMQs (under the widely held Exponential Time Hypothesis). One of the main technical tools introduced in the paper is an fpt-reduction from deciding parameterized uniform CSPs to parameterized OMQ evaluation. A fundamental feature of the reduction is preservation of measures which are known to be essential for classifying classes of parameterized uniform CSPs: submodular width (according to the well known result of Marx for unbounded-arity schemas) and treewidth (according to the well known result of Grohe for bounded-arity schemas). As such, the reduction can be employed to obtain hardness results for evaluation of classes of parameterized OMQs both in the unbounded and in the bounded arity case. Previously, in the case of bounded arity schemas, this has been tackled using a technique requiring full introspection into the construction employed by Grohe.
• Abstract（参考訳）: 本稿では,保護型TGD(GTGDs)と結合型クエリ(UCQs)に基づいてオントロジー媒介クエリ(OMQs)を評価する際のパラメータ化複雑性を,リレーショナルシンボルが非有界なアリティを持ち,パラメータがOMQのサイズであるような環境で解析する。 これは、そのようなOMQの帰納的列挙可能クラスの固定パラメータトラクタビリティ(fpt)評価の正確な基準を(広く保持されている指数時間仮説の下で)確立する。 本論文で紹介する主な技術ツールの1つは、パラメータ化された均一CSPの決定からパラメータ化されたOMQ評価へのfpt-reduceである。 この削減の基本的な特徴は、パラメータ化された一様cspのクラスを分類するのに不可欠な測度の保存である: 部分モジュラ幅(unbounded-arity schemasに対するマルクスのよく知られた結果による)とtreewidth(bounded-arity schemasに対するgroheの既知の結果による)である。 これにより、非有界および有界アリティケースの両方において、パラメータ化OMQのクラスの評価のための硬度結果を得ることができる。 従来、有界アリティスキーマの場合、これはGroheが採用した構造に対する完全なイントロスペクションを必要とする手法を用いて取り組まれてきた。

関連論文リスト

• How to Prune Your Language Model: Recovering Accuracy on the "Sparsity May Cry'' Benchmark [60.72725673114168]
  下流データセットの微調整中における正確なBERTプルーニングの問題を再考する。 そこで我々は,SMCベンチマークの挑戦においても,プルーニングを成功させるための一般的なガイドラインを提案する。
  論文  参考訳（メタデータ） (2023-12-21T03:11:30Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• MM Algorithms to Estimate Parameters in Continuous-time Markov Chains [0.0]
  遷移率をパラメータの集合上の関数とするパラメトリックCTMCについて紹介する。 2つの学習シナリオをカバーするパラメトリックCTMCの反復的推定アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-16T21:25:27Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。 本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。 低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
  論文  参考訳（メタデータ） (2022-11-03T16:42:40Z)
• Probabilistic Entity Representation Model for Chain Reasoning over Knowledge Graphs [18.92547855877845]
  本稿では,知識グラフ上の論理的推論のための確率的エンティティ表現モデル(PERM)を提案する。 PERMは、エンティティを平均と共分散パラメータで多変量ガウス密度としてエンコードし、意味的位置と滑らかな決定境界をキャプチャする。 われわれは, PERMの薬剤再精製事例研究における能力を示すとともに, 提案された研究が, 現行の方法よりもはるかに優れたF1薬剤を推奨できることを実証した。
  論文  参考訳（メタデータ） (2021-10-26T09:26:10Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• Autoregressive Hidden Markov Models with partial knowledge on latent space applied to aero-engines prognostics [2.179313476241343]
  本稿では,ARPHMM(Auto Regressive Partially-hidden Markov Model)を用いて,センサデータに基づく機器の故障検出と予後予測を行う。 健康指標に基づいて,このモデルを用いて残りの生活を推定する方法を示す。
  論文  参考訳（メタデータ） (2021-05-01T10:23:22Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  関係データベース上でのオントロジーによるクエリの評価について検討する。 OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。 また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
  論文  参考訳（メタデータ） (2020-03-17T16:32:00Z)
• The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs [10.042878093985458]
  制約が存在する場合のオントロジーによるクエリとクエリは2つの重要なデータベース問題である。 保護されたTGDとUCQのコンテキストにおける効率的なクエリ評価の限界を実際のクエリとして検討する。
  論文  参考訳（メタデータ） (2019-12-28T11:08:33Z)

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

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