論文の概要: Lower Bounds for the Algorithmic Complexity of Learned Indexes

• arxiv url: http://arxiv.org/abs/2601.06629v1
• Date: Sat, 10 Jan 2026 17:28:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:00.907375
• Title: Lower Bounds for the Algorithmic Complexity of Learned Indexes
• Title（参考訳）: 学習指標のアルゴリズム的複雑度に対する下界
• Authors: Luis Alberto Croquevielle, Roman Sokolovskii, Thomas Heinis,
• Abstract要約: 学習されたインデックス構造は、データベース属性に関連するランク関数を近似するために、機械学習モデルをトレーニングすることでクエリを高速化することを目的としている。 実効性はあるものの、理論上の限界は完全には理解されていない。 本稿では,空間的オーバーヘッドの観点から表現し,近似に使用するモデルクラスによってパラメータ化される,学習指標に対するクエリ時間に対する下界の証明を行うための一般的なフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 5.964436882344729
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute. While effective in practice, their theoretical limitations are not fully understood. We present a general framework for proving lower bounds on query time for learned indexes, expressed in terms of their space overhead and parameterized by the model class used for approximation. Our formulation captures a broad family of learned indexes, including most existing designs, as piecewise model-based predictors. We solve the problem of lower bounding query time in two steps: first, we use probabilistic tools to control the effect of sampling when the database attribute is drawn from a probability distribution. Then, we analyze the approximation-theoretic problem of how to optimally represent a cumulative distribution function with approximators from a given model class. Within this framework, we derive lower bounds under a range of modeling and distributional assumptions, paying particular attention to the case of piecewise linear and piecewise constant model classes, which are common in practical implementations. Our analysis shows how tools from approximation theory, such as quantization and Kolmogorov widths, can be leveraged to formalize the space-time tradeoffs inherent to learned index structures. The resulting bounds illuminate core limitations of these methods.
• Abstract（参考訳）: 学習されたインデックス構造は、データベース属性に関連するランク関数を近似するために、機械学習モデルをトレーニングすることでクエリを高速化することを目的としている。 実効性はあるものの、理論上の限界は完全には理解されていない。 本稿では,空間的オーバーヘッドの観点から表現し,近似に使用するモデルクラスによってパラメータ化される,学習指標に対するクエリ時間に対する下界の証明を行うための一般的なフレームワークを提案する。 我々の定式化は、既存のほとんどの設計を含む、学習されたインデックスの幅広いファミリーを、断片的なモデルベースの予測子として捉えます。 まず、確率分布からデータベース属性が引き出されたときのサンプリングの効果を制御するために確率的ツールを使用する。 そして,与えられたモデルクラスから近似器を用いて累積分布関数を最適に表現する方法に関する近似理論問題を解析する。 このフレームワーク内では、モデリングや分布の仮定の範囲で下位境界を導出し、実際的な実装で一般的な、一意に線形かつ一意に定数なモデルクラスの場合に特に注意を払う。 我々の分析は、量子化やコルモゴロフ幅といった近似理論のツールをどのように利用して学習指標構造に固有の時空トレードオフを定式化できるかを示している。 結果として得られる境界は、これらの手法の中核的な限界を照らす。

関連論文リスト

• General bounds on the quality of Bayesian coresets [13.497835690074151]
  この研究は、KL(Kulback-Leibler)上の一般上界と下界を示す。 下限は、コアセット近似の質に関する基本的な制限を得るために適用される。 上界は最近のサブサンプル最適化手法の性能解析に使用される。
  論文  参考訳（メタデータ） (2024-05-20T04:46:14Z)
• It's All in the Mix: Wasserstein Classification and Regression with Mixed Features [2.2685251390114565]
  我々は、離散的特徴の存在を忠実に説明できる分布的に堅牢な予測モデルを開発し、分析する。 我々のモデルは、離散的特徴の存在に非依存な既存手法を著しく上回り得ることを実証する。
  論文  参考訳（メタデータ） (2023-12-19T15:15:52Z)
• Structured Radial Basis Function Network: Modelling Diversity for Multiple Hypotheses Prediction [51.82628081279621]
  多重モード回帰は非定常過程の予測や分布の複雑な混合において重要である。 構造的放射基底関数ネットワークは回帰問題に対する複数の仮説予測器のアンサンブルとして提示される。 この構造モデルにより, このテッセルレーションを効率よく補間し, 複数の仮説対象分布を近似することが可能であることが証明された。
  論文  参考訳（メタデータ） (2023-09-02T01:27:53Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  カラムワイズモデルを適応的かつ自動的に構成するための一般化反復計算フレームワークを提案する。 既製の学習者,シミュレータ,インターフェースを備えた具体的な実装を提供する。
  論文  参考訳（メタデータ） (2022-06-15T19:10:35Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。 言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
  論文  参考訳（メタデータ） (2022-01-08T00:47:50Z)
• Instance-Based Neural Dependency Parsing [56.63500180843504]
  依存関係解析のための解釈可能な推論プロセスを持つニューラルモデルを開発する。 私たちのモデルはインスタンスベースの推論を採用しており、トレーニングセットのエッジと比較することで、依存関係のエッジを抽出し、ラベル付けします。
  論文  参考訳（メタデータ） (2021-09-28T05:30:52Z)
• Spatial Classification With Limited Observations Based On Physics-Aware Structural Constraint [18.070762916388272]
  限られた特徴観察による空間分類は、機械学習において難しい問題である。 本稿では,各クラスにおけるサンプルの特徴値にマルチモーダル分布を従わせることによって,最近のアプローチを拡張した。 マルチモーダル分布を持つ拡張モデルの学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-08-25T20:07:28Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)

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

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