論文の概要: Sketched Sum-Product Networks for Joins

• arxiv url: http://arxiv.org/abs/2506.14034v1
• Date: Mon, 16 Jun 2025 22:13:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-18 17:34:59.256456
• Title: Sketched Sum-Product Networks for Joins
• Title（参考訳）: ジョイントのためのスケッチド・サム・プロダクツ・ネットワーク
• Authors: Brian Tsan, Abylay Amanbayev, Asoke Datta, Florin Rusu,
• Abstract要約: そこで我々はSum-Product Networksを提案する。 我々は,Fast-AGMSとBound Sketchメソッドを実装した。
• 参考スコア（独自算出の注目度）: 0.8999666725996978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sketches have shown high accuracy in multi-way join cardinality estimation, a critical problem in cost-based query optimization. Accurately estimating the cardinality of a join operation -- analogous to its computational cost -- allows the optimization of query execution costs in relational database systems. However, although sketches have shown high efficacy in query optimization, they are typically constructed specifically for predefined selections in queries that are assumed to be given a priori, hindering their applicability to new queries. As a more general solution, we propose for Sum-Product Networks to dynamically approximate sketches on-the-fly. Sum-Product Networks can decompose and model multivariate distributions, such as relations, as linear combinations of multiple univariate distributions. By representing these univariate distributions as sketches, Sum-Product Networks can combine them element-wise to efficiently approximate the sketch of any query selection. These approximate sketches can then be applied to join cardinality estimation. In particular, we implement the Fast-AGMS and Bound Sketch methods, which have successfully been used in prior work, despite their costly construction. By accurately approximating them instead, our work provides a practical alternative to apply these sketches to query optimization.
• Abstract（参考訳）: ケッチは、コストベースのクエリ最適化において重要な問題であるマルチウェイ結合基数推定において高い精度を示している。 結合演算の基数(計算コストに類似)を正確に推定することで、関係データベースシステムにおけるクエリ実行コストの最適化が可能になる。 しかしながら、スケッチはクエリ最適化において高い有効性を示しているが、一般的には優先順位が与えられると仮定されるクエリの事前定義された選択のために構築され、新しいクエリの適用性を妨げている。 より一般的な解法として,我々はSum-Product Networksを提案し,動的にスケッチをオンザフライで近似する。 Sum-Product Networksは、複数の単変数分布の線形結合として関係のような多変量分布を分解し、モデル化することができる。 これらの単変量分布をスケッチとして表現することで、Sum-Product Networksはそれらを要素的に組み合わせて、クエリ選択のスケッチを効率的に近似することができる。 これらの近似スケッチは、濃度推定を結合するために適用することができる。 特にFast-AGMSとBound Sketchは,コストのかかる構造であるにも関わらず,従来の作業でうまく使われてきた。 代わりにそれらを正確に近似することにより、クエリ最適化にこれらのスケッチを適用するための実用的な代替手段を提供します。

関連論文リスト

• Evolutionary Pre-Prompt Optimization for Mathematical Reasoning [45.461506988071534]
  本稿では,実効的なチェーン・オブ・フォー・プレプロンプトの設計におけるサンプル選択の最適化について検討する。 アルゴリズムの選択は、通常、進化的計算のような比較に基づく手法に有利であり、有効性と実現可能性を大幅に向上させることを示している。
  論文  参考訳（メタデータ） (2024-12-05T16:12:06Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Robust Plan Evaluation based on Approximate Probabilistic Machine Learning [3.0784574277021406]
  本稿ではリスク認識学習アプローチに基づく総合的なフレームワークであるRoq(Roust Query)を提案する。 Roqには、クエリ実行のコストと関連するリスクを予測するために設計された、新しい学習コストモデルが含まれている。 我々は、Roqが、最先端技術と比較して、堅牢なクエリ最適化において大幅に改善されていることを実証した。
  論文  参考訳（メタデータ） (2024-01-26T21:16:37Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。 木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。 JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
  論文  参考訳（メタデータ） (2023-07-21T17:00:06Z)
• FactorJoin: A New Cardinality Estimation Framework for Join Queries [35.22928513918166]
  カーディナリティ推定は、クエリ最適化における最も根本的で難しい問題の1つである。 結合クエリを推定する新しいフレームワークであるFacterJoinを提案する。 評価において、FacterJoinは従来の最先端の学習手法よりも効果的に推定できる。
  論文  参考訳（メタデータ） (2022-12-11T15:51:39Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。 我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。 また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
  論文  参考訳（メタデータ） (2020-02-16T09:01:18Z)

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

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