論文の概要: Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training

• arxiv url: http://arxiv.org/abs/2403.11472v1
• Date: Mon, 18 Mar 2024 04:44:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 16:36:25.774798
• Title: Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training
• Title（参考訳）: メモ型インクリメンタルトレーニングによる文字列キー学習インデックス構造の高速化
• Authors: Minsu Kim, Jinwoo Hwang, Guseul Heo, Seiyeon Cho, Divya Mahajan, Jongse Park,
• Abstract要約: 学習されたインデックスは、機械学習モデルを使用して、キーと対応する位置のマッピングをキー値インデックスで学習する。 更新クエリによって導入された変更を組み込むためには、モデルを頻繁に再トレーニングする必要がある。 SIAと呼ばれるアルゴリズムとハードウェアで設計した文字列キー学習インデックスシステムを開発した。
• 参考スコア（独自算出の注目度）: 16.93830041971135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learned indexes use machine learning models to learn the mappings between keys and their corresponding positions in key-value indexes. These indexes use the mapping information as training data. Learned indexes require frequent retrainings of their models to incorporate the changes introduced by update queries. To efficiently retrain the models, existing learned index systems often harness a linear algebraic QR factorization technique that performs matrix decomposition. This factorization approach processes all key-position pairs during each retraining, resulting in compute operations that grow linearly with the total number of keys and their lengths. Consequently, the retrainings create a severe performance bottleneck, especially for variable-length string keys, while the retrainings are crucial for maintaining high prediction accuracy and in turn, ensuring low query service latency. To address this performance problem, we develop an algorithm-hardware co-designed string-key learned index system, dubbed SIA. In designing SIA, we leverage a unique algorithmic property of the matrix decomposition-based training method. Exploiting the property, we develop a memoization-based incremental training scheme, which only requires computation over updated keys, while decomposition results of non-updated keys from previous computations can be reused. We further enhance SIA to offload a portion of this training process to an FPGA accelerator to not only relieve CPU resources for serving index queries (i.e., inference), but also accelerate the training itself. Our evaluation shows that compared to ALEX, LIPP, and SIndex, a state-of-the-art learned index systems, SIA-accelerated learned indexes offer 2.6x and 3.4x higher throughput on the two real-world benchmark suites, YCSB and Twitter cache trace, respectively.
• Abstract（参考訳）: 学習されたインデックスは、機械学習モデルを使用して、キーと対応する位置のマッピングをキー値インデックスで学習する。 これらのインデックスは、マッピング情報をトレーニングデータとして使用する。 学習されたインデックスは、更新クエリによって導入された変更を組み込むために、モデルの頻繁な再トレーニングを必要とする。 モデルを効率的に再トレーニングするために、既存の学習インデックスシステムは、行列分解を行う線形代数的QR分解技術を利用することが多い。 この分解アプローチは、再トレーニング毎にすべてのキー配置ペアを処理し、結果として、キーの総数とその長さとともに線形に成長する計算処理をもたらす。 その結果、リトレーニングは、特に可変長文字列キーにおいて、厳しいパフォーマンスボトルネックを生じさせ、リトレーニングは高い予測精度を維持する上で不可欠であり、クエリサービスのレイテンシを低くする。 この性能問題に対処するため、SIAと呼ばれるアルゴリズムで設計した文字列キー学習インデックスシステムを開発した。 SIAの設計において,行列分解に基づく学習手法のユニークなアルゴリズム特性を利用する。 本手法では,更新鍵の計算のみを必要とするメモ化に基づく漸進的学習手法を考案し,更新されていない鍵の分解結果を再利用する。 さらに、SIAを拡張して、このトレーニングプロセスの一部をFPGAアクセラレータにオフロードし、インデックスクエリ(推論)を提供するCPUリソースを緩和するだけでなく、トレーニング自体を高速化する。 我々の評価によると、最先端の学習インデックスシステムであるALEX、LIPP、SIndexと比較して、SIAが加速した学習インデックスは、2つの実世界のベンチマークスイートであるYCSBとTwitterのキャッシュトレースに対して、それぞれ2.6倍と3.4倍のスループットを提供する。

関連論文リスト

• Squeezed Attention: Accelerating Long Context Length LLM Inference [64.11145320159126]
  本稿では,入力プロンプトの大部分を固定したLLMアプリケーションを高速化する機構として,Squeezed Attentionを提案する。 K-meansクラスタリングをオフラインで使用して、セマンティックな類似性に基づいて、固定されたコンテキストのキーをグループ化し、各クラスタを単一のセントロイド値で表現します。 そして、固定された文脈から重要なキーのみを用いて正確な注意を計算し、帯域幅と計算コストを削減する。
  論文  参考訳（メタデータ） (2024-11-14T18:54:19Z)
• Exact, Tractable Gauss-Newton Optimization in Deep Reversible Architectures Reveal Poor Generalization [52.16435732772263]
  多くのアプリケーションにおいて、ディープニューラルネットワークのトレーニングを加速する2階最適化が示されている。 しかし、二階法の一般化特性についてはいまだ議論が続いている。 我々は、Gauss-Newton (GN) の正確な更新が、ディープアーキテクチャのクラスにおいて、牽引可能な形式を取ることを初めて示す。
  論文  参考訳（メタデータ） (2024-11-12T17:58:40Z)
• UpLIF: An Updatable Self-Tuning Learned Index Framework [4.077820670802213]
  UpLIFは、入ってくる更新に対応するようにモデルを調整した適応的な自己チューニング学習インデックスである。 また、モデル固有の特性を決定するバランスモデル調整の概念も導入する。
  論文  参考訳（メタデータ） (2024-08-07T22:30:43Z)
• Semi-Parametric Retrieval via Binary Token Index [71.78109794895065]
  Semi-parametric Vocabulary Disentangled Retrieval (SVDR) は、新しい半パラメトリック検索フレームワークである。 既存のニューラル検索手法に似た、高い有効性のための埋め込みベースのインデックスと、従来の用語ベースの検索に似た、迅速かつ費用対効果の高いセットアップを可能にするバイナリトークンインデックスの2つのタイプをサポートする。 埋め込みベースインデックスを使用する場合の高密度検索器DPRよりも3%高いトップ1検索精度と、バイナリトークンインデックスを使用する場合のBM25よりも9%高いトップ1検索精度を実現する。
  論文  参考訳（メタデータ） (2024-05-03T08:34:13Z)
• Accelerating Matrix Factorization by Dynamic Pruning for Fast Recommendation [0.49399484784577985]
  MF(Matrix Factorization)は、リコメンデーションシステム(RS)のための協調フィルタリングアルゴリズムである。 現在のRSではユーザ/イテムが劇的に増加しているため、MFモデルのトレーニングに要する計算の複雑さは大幅に増大している。 我々は、追加の計算資源を誘導することなく、MFを高速化するアルゴリズム手法を提案する。
  論文  参考訳（メタデータ） (2024-03-18T16:27:33Z)
• NFL: Robust Learned Index via Distribution Transformation [14.812854942243503]
  本稿では、学習インデックスを構築する前に、鍵にテキスト分布変換を適用することで近似問題に取り組む。 2段階の正規化フローベース学習インデックスフレームワーク (NFL) が提案され、最初に元の複雑な鍵分布をほぼ一様に変換し、次に変換された鍵を利用する学習インデックスを構築する。 変換キーの特性に基づいて、ロバストなアフターフロー学習指標(AFLI)を提案する。
  論文  参考訳（メタデータ） (2022-05-24T06:03:19Z)
• CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm [1.9798034349981157]
  Recursive Model Index (RMI) フレームワークの効率を改善するために,キャッシュ認識型学習インデックス (CARMI) の設計を提案する。 学習指標の最適設計を最適化問題として探索する問題を定式化し,それを解くための動的プログラミングアルゴリズムを提案する。 実験の結果,ベースラインよりも高い性能でインデックスを構築することができることがわかった。
  論文  参考訳（メタデータ） (2021-03-01T09:20:53Z)
• COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies [3.670422696827525]
  データセットの属性間の相関関係を学習する多次元データのための学習指標であるCOAXを提案する。 実験により,データ中の関連属性を予測することにより,クエリ実行時間を短縮し,インデックスのメモリオーバーヘッドを低減することができることがわかった。
  論文  参考訳（メタデータ） (2020-06-29T21:22:15Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。 本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
  論文  参考訳（メタデータ） (2020-04-30T18:09:50Z)
• Post-Estimation Smoothing: A Simple Baseline for Learning with Side Information [102.18616819054368]
  本稿では,構造指標データを予測に組み込む高速かつ効率的な手法として,後推定平滑化演算子を提案する。 滑らかなステップは元の予測器とは分離されているため、機械学習タスクの幅広いクラスに適用できる。 大規模な空間的・時間的データセットに関する実験は,実測後のスムース化の速度と正確さを浮き彫りにした。
  論文  参考訳（メタデータ） (2020-03-12T18:04:20Z)
• On Coresets for Support Vector Machines [61.928187390362176]
  coresetは、元のデータポイントの小さな、代表的なサブセットである。 我々は,本アルゴリズムを用いて,既製のSVMソルバをストリーミング,分散,動的データ設定に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-15T23:25:12Z)

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

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