論文の概要: Enhancing Datalog Reasoning with Hypertree Decompositions

• arxiv url: http://arxiv.org/abs/2305.06854v2
• Date: Mon, 15 May 2023 12:57:50 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-16 11:05:49.289830
• Title: Enhancing Datalog Reasoning with Hypertree Decompositions
• Title（参考訳）: ハイパーツリー分解によるデータログ推論の強化
• Authors: Xinyue Zhang, Pan Hu, Yavor Nenov, Ian Horrocks
• Abstract要約: データログプログラムの物質化と漸進的評価にハイパーツリー分解を利用するアルゴリズムを提供する。 このアプローチを標準データログ推論アルゴリズムとモジュール方式で組み合わせることで,分解によるオーバーヘッドを低減する。
• 参考スコア（独自算出の注目度）: 17.868595375154506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Datalog reasoning based on the semina\"ive evaluation strategy evaluates rules using traditional join plans, which often leads to redundancy and inefficiency in practice, especially when the rules are complex. Hypertree decompositions help identify efficient query plans and reduce similar redundancy in query answering. However, it is unclear how this can be applied to materialisation and incremental reasoning with recursive Datalog programs. Moreover, hypertree decompositions require additional data structures and thus introduce nonnegligible overhead in both runtime and memory consumption. In this paper, we provide algorithms that exploit hypertree decompositions for the materialisation and incremental evaluation of Datalog programs. Furthermore, we combine this approach with standard Datalog reasoning algorithms in a modular fashion so that the overhead caused by the decompositions is reduced. Our empirical evaluation shows that, when the program contains complex rules, the combined approach is usually significantly faster than the baseline approach, sometimes by orders of magnitude.
• Abstract（参考訳）: セミナイブ評価戦略に基づくデータログ推論は、従来のジョインプランを使用してルールを評価し、特にルールが複雑である場合、実際には冗長性と非効率性をもたらすことが多い。 ハイパーツリー分解は、効率的なクエリ計画を特定し、クエリ応答における類似の冗長性を低減します。 しかし、再帰的データログプログラムによる実体化や漸進的推論にどのように適用できるかは不明である。 さらに、ハイパーツリーの分解には追加のデータ構造が必要であるため、実行時とメモリ消費の両方で無視できないオーバーヘッドが発生する。 本稿では,データログプログラムの実体化とインクリメンタル評価にハイパーツリー分解を利用するアルゴリズムを提案する。 さらに,本手法を標準データログ推論アルゴリズムとモジュール方式で組み合わせることで,分解によるオーバーヘッドを低減する。 私たちの経験的評価は、プログラムが複雑な規則を含む場合、組み合わせたアプローチは、しばしば桁違いの順序で、ベースラインアプローチよりもはるかに高速であることを示している。

関連論文リスト

• Fuzzy Datalog$^\exists$ over Arbitrary t-Norms [5.464669506214195]
  ニューロ・シンボリックAIの領域における大きな課題の1つは、ニューラルデータとシンボリックデータの両方の存在下で論理的推論を行うことである。 これは知識グラフ、ニューラルモデル予測、構造化データベース、クラウドソースデータなどの異種データソースを組み合わせる必要がある。 規則体における古典的な接続の代わりとして任意のt-ノルムを許容することにより、規則ベースの標準言語Datalogをその設定に存在規則で一般化する。 結果のフォーマリズムにより、計算複雑性結果の保存と確立された推論技術の適用性を保ちながら、関連するデータを不確実性の度合いで推論することが可能となる。
  論文  参考訳（メタデータ） (2024-03-05T12:51:40Z)
• ZodiacEdge: a Datalog Engine With Incremental Rule Set Maintenance [0.0]
  ルールセットの更新が可能となると、Datalog推論の実体化の漸進的なメンテナンスに取り組む。 これはモノのインターネットとエッジコンピューティングの文脈において特に重要であり、スマートデバイスはデータログルールに代表される新しい知識を推論する必要があるかもしれない。 提案手法は,ノードがデータログプログラムのルールセットに対応する依存ハイパーグラフに適用される階層化戦略の適応に基づく。
  論文  参考訳（メタデータ） (2023-12-22T08:53:48Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  本稿では,論理的推論の基盤として,対話レベルと単語レベルの両方の文脈を扱う総合グラフネットワーク(HGN)を提案する。 具体的には、ノードレベルの関係とタイプレベルの関係は、推論過程におけるブリッジと解釈できるが、階層的な相互作用機構によってモデル化される。
  論文  参考訳（メタデータ） (2023-06-21T07:34:27Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• An Efficient Incremental Simple Temporal Network Data Structure for Temporal Planning [7.835452825434851]
  時間的計画問題の解法の一つは、因果決定を分離し、時間的決定から時間的決定へ、それらを単純な時間的ネットワーク(STN)解決器に求めることである。 本稿では,STNが時間的計画においてどのように使用されるのかを詳述し,このユースケースをサポートするための明確なインターフェースを特定し,時間的・メモリ効率の両面から,このインターフェースを実装する効率的なデータ構造を提案する。 デルタステンと呼ばれる我々のデータ構造は、時間的計画順序に関する他の最先端のアプローチよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-12-14T13:57:37Z)
• Seminaive Materialisation in DatalogMTL [10.850687097496373]
  DatalogMTLは、計量時間演算子を備えたDatalogの拡張である。 本稿では,冗長計算を最小化するための物質化に基づく手法を提案する。 実験の結果,DatalogMTLの最適化セミナティブ戦略により,製造時間を大幅に短縮できることがわかった。
  論文  参考訳（メタデータ） (2022-08-15T10:04:44Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  相互依存信号のデータセットは、列が強い依存を示す行列として定義される。 ニューラルネットワークは、事前に構造として機能し、基礎となる信号相互依存性を明らかにするために使用される。 ディープ・アンローリングとディープ・平衡に基づくアルゴリズムが開発され、高度に解釈可能で簡潔なディープ・ラーニング・ベース・アーキテクチャを形成する。
  論文  参考訳（メタデータ） (2022-03-29T21:00:39Z)
• Complexity of Arithmetic in Warded Datalog+- [1.5469452301122173]
  Warded Datalog+- ロジックベースの言語Datalogを拡張し、ルールヘッドに存在量化器を配置する。 我々はWarded Datalog+を算術演算で拡張し、P完全性を証明する新しい言語を定義する。 我々は,新たに定義された言語に対する効率的な推論アルゴリズムを提案し,最近導入された整数演算を用いたデータログフラグメントの記述的複雑性を証明した。
  論文  参考訳（メタデータ） (2022-02-10T15:14:03Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption [127.439030701253]
  確率感性決定図は構造化分解可能な回路のクラスである。 本稿では,回路の論理的基盤を暗黙的に提供する部分閉世界仮定に基づく新しいスキームを提案する。 予備実験では、提案手法がトレーニングデータに適切に適合し、基礎となる論理的基盤と整合性を維持した上で、テストデータによく適合することを示した。
  論文  参考訳（メタデータ） (2021-07-26T12:01:56Z)

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

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