論文の概要: Approximate Aggregate Queries Under Additive Inequalities

• arxiv url: http://arxiv.org/abs/2003.10588v2
• Date: Thu, 30 Apr 2020 20:52:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-20 09:43:22.338989
• Title: Approximate Aggregate Queries Under Additive Inequalities
• Title（参考訳）: 付加的不等式による近似集約クエリ
• Authors: Mahmoud Abo-Khamis and Sungjin Im and Benjamin Moseley and Kirk Pruhs and Alireza Samadian
• Abstract要約: 本稿では, 付加的不等式を考慮した関係データに対して, ある種の機能的集約クエリを評価することの問題点について考察する。 まず、ある加法不等式の場合であっても、問題はNPハードであることが示される。 我々の主な成果は近似の効率的なアルゴリズムであり、相対誤差は任意に小さく、1つの加法不等式を持つ自然集合クエリが多数存在する。
• 参考スコア（独自算出の注目度）: 15.338931971492288
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of evaluating certain types of functional aggregation queries on relational data subject to additive inequalities. Such aggregation queries, with a smallish number of additive inequalities, arise naturally/commonly in many applications, particularly in learning applications. We give a relatively complete categorization of the computational complexity of such problems. We first show that the problem is NP-hard, even in the case of one additive inequality. Thus we turn to approximating the query. Our main result is an efficient algorithm for approximating, with arbitrarily small relative error, many natural aggregation queries with one additive inequality. We give examples of natural queries that can be efficiently solved using this algorithm. In contrast, we show that the situation with two additive inequalities is quite different, by showing that it is NP-hard to evaluate simple aggregation queries, with two additive inequalities, with any bounded relative error.
• Abstract（参考訳）: 付加的不等式を対象とする関係データに対するある種の機能集約クエリの評価の問題を考える。 このようなアグリゲーションクエリは、加法的不等式が小さいが、多くのアプリケーション、特に学習アプリケーションで自然に発生する。 このような問題の計算の複雑さを比較的完全に分類する。 まず、ある加法不等式の場合であっても、問題はNPハードであることを示す。 したがって、クエリを近似します。 我々の主な結果は、任意に小さな相対誤差と1つの加法不等式を持つ多数の自然集約クエリを近似する効率的なアルゴリズムである。 このアルゴリズムを用いて効率的に解ける自然クエリの例を示す。 対照的に、2つの加法不等式を持つ状況は、有界な相対誤差を持つ2つの加法不等式を持つ単純なアグリゲーションクエリを評価するのがnp困難であることを示すことにより、かなり異なる。

関連論文リスト

• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  階層モデルに基づく選好文の一貫性問題の解法として,アルゴリズム的手法を構築し,比較する。 インスタンスが一貫すると、評価関数に階層的モデルが存在し、代替関数の順序関係を誘導する。 この問題を解決するための3つのアプローチを開発する。
  論文  参考訳（メタデータ） (2024-10-31T13:48:46Z)
• MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
  大規模言語モデル(LLM)は、高い精度で算術語問題を解くことができるが、訓練された言語よりも複雑な問題にどのように一般化するかは、ほとんど分かっていない。 本研究では、任意に複雑な算術証明問題に対する LLM の評価フレームワーク、MathGAP を提案する。
  論文  参考訳（メタデータ） (2024-10-17T12:48:14Z)
• Primal Methods for Variational Inequality Problems with Functional Constraints [25.261426717550293]
  本稿では,関数的制約付き変分不等式問題に対処する手法として,制約付き勾配法(Constrained Gradient Method, CGM)を提案する。 滑らかな制約下での単調作用素による変分不等式問題に対するアルゴリズムの非漸近収束解析を確立する。 提案アルゴリズムは, 単調・強単調両方の演算子問合せにおいて, プロジェクションに基づく手法の複雑さに適合する。
  論文  参考訳（メタデータ） (2024-03-19T16:03:03Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms [2.050873301895484]
  線形順序付け問題(LOP)は、Mオブジェクトをペア比較から順序付けするものである。 我々はスレーター指数を一般化するスレータースペクトルの概念を導入する。 我々は、Mの適度な値に対して管理可能な複雑性O(M3 2M)のスペクトルを求めるアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2022-08-08T01:39:26Z)
• On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
  ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。 バイマックス性能問題を解くための優れた外挿が得られることが示されている。
  論文  参考訳（メタデータ） (2022-01-19T16:14:27Z)
• How to Approximate Ontology-Mediated Queries [22.99749220980996]
  ALC と ALCI の記述論理に基づいて,オントロジーによるクエリに対する近似のいくつかの概念を紹介し,研究する。 近似式は,(1) オントロジーを ELI や特定の TGD などのトラクタブル言語で定式化された1つに置き換える,(2) ツリー幅が定数で有界なデータベースのクラスのようなトラクタブルクラスの1つに置き換える,の2種類からなる。
  論文  参考訳（メタデータ） (2021-07-12T12:29:50Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• Logic Embeddings for Complex Query Answering [56.25151854231117]
  skolemisationを用いて効率的なクエリのための存在変数を排除する、複雑なクエリを組み込む新しいアプローチであるlogic embeddedsを提案する。 論理組込みは,大規模で不完全な知識グラフ上でのクエリ応答において競争的に高速かつ正確であり,否定的問合せよりも優れており,特に回答の不確かさのモデリングが向上している。
  論文  参考訳（メタデータ） (2021-02-28T07:52:37Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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