論文の概要: Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis

• arxiv url: http://arxiv.org/abs/2506.20139v1
• Date: Wed, 25 Jun 2025 05:20:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-26 21:00:42.610901
• Title: Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis
• Title（参考訳）: 学習指標構造における最適線形近似:理論的および経験的解析
• Authors: Jiayong Qin, Xianyu Zhu, Qiyu Liu, Guangyi Zhang, Zhigang Cai, Jianwei Liao, Sha Hu, Jingshu Peng, Yingxia Shao, Lei Chen,
• Abstract要約: Piecewise Linear Approximation (epsilon$-PLA)は、その単純さと有効性から人気がある。 多くの学習指標において中心的な役割を担っているにもかかわらず、$epsilon$-PLA適合アルゴリズムの設計と解析は未解明のままである。
• 参考スコア（独自算出の注目度）: 16.350750984598797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A growing trend in the database and system communities is to augment conventional index structures, such as B+-trees, with machine learning (ML) models. Among these, error-bounded Piecewise Linear Approximation ($\epsilon$-PLA) has emerged as a popular choice due to its simplicity and effectiveness. Despite its central role in many learned indexes, the design and analysis of $\epsilon$-PLA fitting algorithms remain underexplored. In this paper, we revisit $\epsilon$-PLA from both theoretical and empirical perspectives, with a focus on its application in learned index structures. We first establish a fundamentally improved lower bound of $\Omega(\kappa \cdot \epsilon^2)$ on the expected segment coverage for existing $\epsilon$-PLA fitting algorithms, where $\kappa$ is a data-dependent constant. We then present a comprehensive benchmark of state-of-the-art $\epsilon$-PLA algorithms when used in different learned data structures. Our results highlight key trade-offs among model accuracy, model size, and query performance, providing actionable guidelines for the principled design of future learned data structures.
• Abstract（参考訳）: データベースやシステムコミュニティのトレンドは、B+ツリーのような従来のインデックス構造を機械学習(ML)モデルで強化することです。 これらのうち、エラーバウンドなPiecewise Linear Approximation(\epsilon$-PLA)は、その単純さと有効性から人気がある。 多くの学習指標において中心的な役割を担っているにもかかわらず、$\epsilon$-PLA適合アルゴリズムの設計と解析は未定のままである。 本稿では,理論的および経験的両視点から$\epsilon$-PLAを再考し,その学習指標構造への応用に焦点をあてる。 まず、既存の$\epsilon$-PLA適合アルゴリズムのセグメントカバレッジについて、基本的に改善された$\Omega(\kappa \cdot \epsilon^2)$を定めます。 次に、異なる学習データ構造で使用される場合、最先端の$\epsilon$-PLAアルゴリズムの包括的なベンチマークを示す。 この結果から,モデル精度,モデルサイズ,クエリ性能などの重要なトレードオフを浮き彫りにし,将来的な学習データ構造の設計に関する実用的なガイドラインを提供する。

関連論文リスト

• Learning Identifiable Structures Helps Avoid Bias in DNN-based Supervised Causal Learning [56.22841701016295]
  Supervised Causal Learning (SCL)はこの分野で新興パラダイムである。 既存のディープニューラルネットワーク(DNN)ベースの手法では、"Node-Edgeアプローチ"が一般的である。
  論文  参考訳（メタデータ） (2025-02-15T19:10:35Z)
• Revisiting Nearest Neighbor for Tabular Data: A Deep Tabular Baseline Two Decades Later [76.66498833720411]
  K$-nearest neighbors (KNN) はもともと,インスタンス間のセマンティックな類似性を捉えるために線形投影を学習するために設計されたものだ。 意外なことに、SGDを用いたNAAの実装と次元減少のない実装は、表データの良好な性能をすでに達成しています。 本稿では、損失関数、予測戦略、深いアーキテクチャなど、これらの改善の背景にある要因を分析して、論文を締めくくる。
  論文  参考訳（メタデータ） (2024-07-03T16:38:57Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Surprisal Driven $k$-NN for Robust and Interpretable Nonparametric Learning [1.4293924404819704]
  我々は情報理論の観点から、隣り合う従来のアルゴリズムに新たな光を当てた。 単一モデルを用いた分類,回帰,密度推定,異常検出などのタスクに対する頑健で解釈可能なフレームワークを提案する。 我々の研究は、分類と異常検出における最先端の成果を達成することによって、アーキテクチャの汎用性を示す。
  論文  参考訳（メタデータ） (2023-11-17T00:35:38Z)
• Principled and Efficient Motif Finding for Structure Learning of Lifted Graphical Models [5.317624228510748]
  構造学習は、ニューロシンボリックAIと統計リレーショナル学習の分野の中心となるAIの中核的な問題である。 昇降型グラフィカルモデルにおける構造モチーフのマイニングのための第一原理的アプローチを提案する。 我々は,最先端構造学習の手法を,精度で最大6%,実行時の最大80%で上回ることを示す。
  論文  参考訳（メタデータ） (2023-02-09T12:21:55Z)
• 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)
• Learning to Learn Graph Topologies [27.782971146122218]
  ノードデータからグラフ構造へのマッピングを学習する(L2O)。 このモデルは、ノードデータとグラフサンプルのペアを使ってエンドツーエンドでトレーニングされる。 合成データと実世界のデータの両方の実験により、我々のモデルは、特定のトポロジ特性を持つグラフを学習する際の古典的反復アルゴリズムよりも効率的であることが示された。
  論文  参考訳（メタデータ） (2021-10-19T08:42:38Z)
• The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures [9.567119607658299]
  本研究は,学習指標構造に対する毒素攻撃に関する最初の研究である。 累積分布関数に基づいて学習した線形回帰モデルに対する最初の中毒攻撃を定式化する。 我々は,本手法を一般化し,学習指標構造のより先進的な2段階設計に対処する。
  論文  参考訳（メタデータ） (2020-08-01T17:12:04Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)

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

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