論文の概要: Exploiting Database Management Systems and Treewidth for Counting

• arxiv url: http://arxiv.org/abs/2001.04191v2
• Date: Wed, 3 Feb 2021 16:54:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-11 23:41:43.946562
• Title: Exploiting Database Management Systems and Treewidth for Counting
• Title（参考訳）: データベース管理システムとtreewidthを利用したカウント
• Authors: Johannes K. Fichte, Markus Hecher, Patrick Thier, Stefan Woltran
• Abstract要約: 正規カウント問題は#SATであり、ブール公式の割り当てを数えるように求めている。 最近の研究によると、#SATのベンチマークインスタンスは、適度に小さなツリー幅を持つことが多い。 本稿では,最先端データベース管理システムに基づく質問数解決のための一般的なフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 22.315022989618594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #SAT, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #SAT often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.
• Abstract（参考訳）: 境界木幅は最も引用される組合せ不変量の一つであり、いくつかの数え上げ問題を効率的に解くために文献に応用された。 正規カウント問題は#SATであり、ブール公式の満足な割り当てを数えるように求めている。 最近の研究によると、#SATのベンチマークインスタンスは比較的小さなツリー幅を持つことが多い。 本稿では,小さな木幅の場合の計数問題を扱う。 本稿では,DBMS(State-of-the-art database management system)に基づく質問数解決のための一般的なフレームワークを提案する。 我々のフレームワークは、木分解(TD)における動的プログラミング(DP)を用いてインスタンスを解くことで、小さな木幅を明示的に活用する。 したがって、DPアルゴリズムは理論上テーブル操作の点ですでによく使われているため、DPの概念をDBMS(PostgreSQL)に実装する。 これにより、dpアルゴリズムのエレガントな仕様と、レコードやテーブルを操作するsqlの使用が可能になり、dpアルゴリズムを実践するための自然なアプローチが得られます。 最善の知識を得るために,我々はtdsのアルゴリズムにdbmsを用いる最初の手法を提案する。 このアプローチの重要な利点は、DBMSが自然に、メインメモリ(RAM)が限られている巨大なテーブルを扱えること、並列化、計算の停止が可能であることです。

関連論文リスト

• FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
  インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。 既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。 本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
  論文  参考訳（メタデータ） (2024-06-06T04:05:54Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
  本研究では、動的プログラミング(DP)にインスパイアされた最大独立集合(MIS)問題を解決するグラフニューラルネットワーク(GNN)フレームワークを提案する。 GNNをベースとしたDPライクな再帰アルゴリズムを提案し、まず2つの小さなサブグラフを構築し、より大きなMISを持つサブグラフを予測し、次に再帰呼び出しを行う。 MISサイズに関する異なるグラフの比較を注釈付けすると、自己学習プロセスが発生し、比較をより正確に自己アノテーションし、その逆も引き起こされる。
  論文  参考訳（メタデータ） (2023-10-28T10:58:25Z)
• DP-starJ: A Differential Private Scheme towards Analytical Star-Join Queries [10.022473569166532]
  Star-joinクエリはデータウェアハウスの基本的なタスクであり、オンライン分析処理(OLAP)のシナリオに幅広い応用がある。 本稿では,スタージョインクエリのための新しい微分プライベートフレームワークDP-starJを提案する。
  論文  参考訳（メタデータ） (2023-10-07T07:05:52Z)
• Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
  予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。 いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
  論文  参考訳（メタデータ） (2023-05-30T17:02:07Z)
• Uni-Parser: Unified Semantic Parser for Question Answering on Knowledge Base and Database [86.03294330305097]
  知識ベース(KB)とデータベース(DB)の両方で質問応答(QA)を統一した意味的要素を提案する。 フレームワークに不可欠な要素としてプリミティブ(KBのリレーションとエンティティ、テーブル名、列名、DBのセル値)を導入します。 生成元を利用して、異なる操作でトップランクプリミティブを変更・構成することで、最終的な論理形式を予測する。
  論文  参考訳（メタデータ） (2022-11-09T19:33:27Z)
• Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract [9.480212602202517]
  この研究は、論理ベースの問題とツリー幅ベースの方法とそれを解決するツールに焦点を当てている。 本稿では,分解誘導(DG)による新しいタイプの問題削減について述べる。 木幅を直接利用して,Satの拡張を効率的に解くアルゴリズムを実装した。
  論文  参考訳（メタデータ） (2022-08-24T07:43:58Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。 提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
  論文  参考訳（メタデータ） (2022-02-22T01:34:35Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)

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

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