論文の概要: 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倍のスループットを提供する。
関連論文リスト
- 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) - Constructing Tree-based Index for Efficient and Effective Dense
Retrieval [26.706985694158384]
JTRは、TReeベースのインデックスとクエリエンコーディングの合同最適化の略である。
我々は、木に基づくインデックスとクエリエンコーダをエンドツーエンドにトレーニングするために、新しい統合されたコントラスト学習損失を設計する。
実験結果から,JTRは高いシステム効率を維持しつつ,検索性能が向上することが示された。
論文 参考訳(メタデータ) (2023-04-24T09:25:39Z) - 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) - Fast Few-Shot Classification by Few-Iteration Meta-Learning [173.32497326674775]
数ショット分類のための高速な最適化に基づくメタラーニング手法を提案する。
我々の戦略はメタ学習において学習すべき基礎学習者の目的の重要な側面を可能にする。
我々は、我々のアプローチの速度と効果を実証し、総合的な実験分析を行う。
論文 参考訳(メタデータ) (2020-10-01T15:59:31Z) - COAX: Correlation-Aware Indexing on Multidimensional Data with Soft
Functional Dependencies [3.670422696827525]
データセットの属性間の相関関係を学習する多次元データのための学習指標であるCOAXを提案する。
実験により,データ中の関連属性を予測することにより,クエリ実行時間を短縮し,インデックスのメモリオーバーヘッドを低減することができることがわかった。
論文 参考訳(メタデータ) (2020-06-29T21:22:15Z) - AdaS: Adaptive Scheduling of Stochastic Gradients [50.80697760166045]
我々は、textit "knowledge gain" と textit "mapping condition" の概念を導入し、Adaptive Scheduling (AdaS) と呼ばれる新しいアルゴリズムを提案する。
実験によると、AdaSは派生した指標を用いて、既存の適応学習手法よりも高速な収束と優れた一般化、そして(b)いつトレーニングを中止するかを決定するための検証セットへの依存の欠如を示す。
論文 参考訳(メタデータ) (2020-06-11T16:36:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。