論文の概要: Extending Sticky-Datalog+/- via Finite-Position Selection Functions:
Tractability, Algorithms, and Optimization
- arxiv url: http://arxiv.org/abs/2108.00903v2
- Date: Tue, 3 Aug 2021 02:52:18 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-04 09:17:31.460837
- Title: Extending Sticky-Datalog+/- via Finite-Position Selection Functions:
Tractability, Algorithms, and Optimization
- Title（参考訳）: 有限ポジション選択関数によるSticky-Datalog+/-の拡張:トラクタビリティ、アルゴリズム、最適化
- Authors: Leopoldo Bertossi, Mostafa Milani
- Abstract要約: 我々は,追跡手順の動作の観点から,Sticky と WS プログラムについて検討する。
クラスsch(S)におけるプログラムに対するボトムアップQAアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 3.4621178017146543
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Weakly-Sticky(WS) Datalog+/- is an expressive member of the family of
Datalog+/- program classes that is defined on the basis of the conditions of
stickiness and weak-acyclicity. Conjunctive query answering (QA) over the WS
programs has been investigated, and its tractability in data complexity has
been established. However, the design and implementation of practical QA
algorithms and their optimizations have been open. In order to fill this gap,
we first study Sticky and WS programs from the point of view of the behavior of
the chase procedure. We extend the stickiness property of the chase to that of
generalized stickiness of the chase (GSCh) modulo an oracle that selects (and
provides) the predicate positions where finitely values appear during the
chase. Stickiness modulo a selection function S that provides only a subset of
those positions defines sch(S), a semantic subclass of GSCh. Program classes
with selection functions include Sticky and WS, and another syntactic class
that we introduce and characterize, namely JWS, of jointly-weakly-sticky
programs, which contains WS. The selection functions for these last three
classes are computable, and no external, possibly non-computable oracle is
needed. We propose a bottom-up QA algorithm for programs in the class sch(S),
for a general selection function S. As a particular case, we obtain a
polynomial-time QA algorithm for JWS and weakly-sticky programs. Unlike WS, JWS
turns out to be closed under magic-sets query optimization. As a consequence,
both the generic polynomial-time QA algorithm and its magic-set optimization
can be particularized and applied to WS.
- Abstract（参考訳）: weakly-sticky(ws) datalog+/-は、粘着性と非循環性の条件に基づいて定義されるdatalog+/-プログラムクラスの表現力のあるメンバーである。
WS プログラム上での接続型クエリ応答 (QA) について検討し,データ複雑性のトラクタビリティを確立した。
しかし,実効的なQAアルゴリズムの設計と実装とその最適化は未完成である。
このギャップを埋めるために、私たちはまず、追跡手順の振る舞いの観点から、StickyとWSプログラムを研究します。
我々は、チェイスのスティッキネス特性を、チェイス中に有限の値が現れる述語位置を選択する(そして提供する)オラクルの一般化されたスティッキネス(gsch)モジュロに拡張する。
これらの位置のサブセットのみを提供する選択関数 S の粘度変調は、GSCh のセマンティックサブクラス sch(S) を定義する。
選択関数を持つプログラムクラスには、Sticky と WS と、WS を含むジョイント弱スティックプログラムの導入と特徴付けを行う別の構文クラス、すなわち JWS がある。
これら3つのクラスの選択関数は計算可能であり、外部の計算不可能なオラクルは必要ない。
本稿では,一般選択関数 s に対するクラス sch(s) におけるプログラムのボトムアップ qa アルゴリズムを提案する。
WSと異なり、JWSはマジックセットのクエリ最適化の下でクローズされている。
その結果、一般的な多項式時間QAアルゴリズムとマジックセット最適化の両方を具体化し、WSに適用することができる。
関連論文リスト
- IDEAL: Leveraging Infinite and Dynamic Characterizations of Large Language Models for Query-focused Summarization [59.06663981902496]
クエリ中心の要約(QFS)は、特定の関心事に答え、より優れたユーザ制御とパーソナライゼーションを可能にする要約を作成することを目的としている。
本稿では,LLMを用いたQFSモデル,Longthy Document Summarization,およびクエリ-LLMアライメントの2つの重要な特徴について検討する。
これらのイノベーションは、QFS技術分野における幅広い応用とアクセシビリティの道を開いた。
論文 参考訳（メタデータ） (2024-07-15T07:14:56Z) - FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。
既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。
本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
論文 参考訳（メタデータ） (2024-06-06T04:05:54Z) - Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars [66.823588073584]
大規模言語モデル(LLM)は、現実世界のアプリケーションで印象的な機能を示している。
これらの卓越した作品の品質は、パフォーマンスに大きな影響を与えます。
既存の方法は、先行注文がパフォーマンスに与える影響を適切に説明できない。
論文 参考訳（メタデータ） (2024-05-25T08:23:05Z) - Graph-Based Automatic Feature Selection for Multi-Class Classification
via Mean Simplified Silhouette [4.786337974720721]
本稿では,自動特徴選択のためのグラフベースの新しいフィルタ手法を提案する(略してGB-AFS)。
予測性能を維持するために必要な特徴の最小の組み合わせを決定する。
選択する機能の数など、ユーザ定義パラメータを一切必要としない。
論文 参考訳（メタデータ） (2023-09-05T14:37:31Z) - An Algorithm and Complexity Results for Causal Unit Selection [16.307996243413967]
単位選択問題は、刺激を受ける際に望ましい振る舞いを示す可能性が最も高い、単位と呼ばれる物体を特定することを目的としている。
本稿では,幅広い因果的目的関数のクラスと完全に定義された構造因果的モデルに与えられた最適単位を求めるための,最初の正確なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-28T08:46:51Z) - Explainable Model-specific Algorithm Selection for Multi-Label
Classification [6.442438468509492]
MLC(Multi-label classification)は、データインスタンスが同時に複数のクラスに属すことができる予測モデリングのMLタスクである。
いくつかのMLCアルゴリズムが文献で提案されており、メタ最適化の問題を引き起こしている。
本研究では,データセットの特性を利用した自動アプローチの品質について検討する。
論文 参考訳（メタデータ） (2022-11-21T07:42:11Z) - Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners [0.0]
そこで本研究では,文字列品質の選択を直接正規言語に組み込む,コアスパンナーの代替手法を提案する。
コアスパンナーの断片は、コアスパンナーの完全なクラスよりもわずかに表現力の弱いものの、情報抽出のための文字列平等選択の直感的な応用をカバーしている。
論文 参考訳（メタデータ） (2020-10-26T09:27:39Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z) - Multi-layer Optimizations for End-to-End Data Analytics [71.05611866288196]
代替アプローチを実現するフレームワークであるIFAQ(Iterative Functional Aggregate Queries)を紹介する。
IFAQは、特徴抽出クエリと学習タスクを、IFAQのドメイン固有言語で与えられた1つのプログラムとして扱う。
IFAQ の Scala 実装が mlpack,Scikit,特殊化を数桁で上回り,線形回帰木モデルや回帰木モデルを複数の関係データセット上で処理可能であることを示す。
論文 参考訳（メタデータ） (2020-01-10T16:14:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。