論文の概要: Learned LSM-trees: Two Approaches Using Learned Bloom Filters

• arxiv url: http://arxiv.org/abs/2508.00882v1
• Date: Thu, 24 Jul 2025 04:23:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-10 09:30:49.292225
• Title: Learned LSM-trees: Two Approaches Using Learned Bloom Filters
• Title（参考訳）: 学習されたLSM木:学習されたブルームフィルタを用いた2つのアプローチ
• Authors: Nicholas Fidalgo, Puyuan Ye,
• Abstract要約: キーバリューストアは書き込み最適化のためにログ構造化マージ(LSM)木に大きく依存している。 Bloomフィルタのような補助構造は役に立つが、ツリーの深さとデータセットサイズでスケールするメモリコストを課す。 学習データ構造の最近の進歩は、機械学習モデルがこれらのコンポーネントを拡張したり置き換えたりする可能性があることを示唆している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern key-value stores rely heavily on Log-Structured Merge (LSM) trees for write optimization, but this design introduces significant read amplification. Auxiliary structures like Bloom filters help, but impose memory costs that scale with tree depth and dataset size. Recent advances in learned data structures suggest that machine learning models can augment or replace these components, trading handcrafted heuristics for data-adaptive behavior. In this work, we explore two approaches for integrating learned predictions into the LSM-tree lookup path. The first uses a classifier to selectively bypass Bloom filter probes for irrelevant levels, aiming to reduce average-case query latency. The second replaces traditional Bloom filters with compact learned models and small backup filters, targeting memory footprint reduction without compromising correctness. We implement both methods atop a Monkey-style LSM-tree with leveled compaction, per-level Bloom filters, and realistic workloads. Our experiments show that the classifier reduces GET latency by up to 2.28x by skipping over 30% of Bloom filter checks with high precision, though it incurs a modest false-negative rate. The learned Bloom filter design achieves zero false negatives and retains baseline latency while cutting memory usage per level by 70-80%. Together, these designs illustrate complementary trade-offs between latency, memory, and correctness, and highlight the potential of learned index components in write-optimized storage systems.
• Abstract（参考訳）: 現代のキーバリューストアは書き込み最適化のためにログ構造化マージ(LSM)木に大きく依存しているが、この設計では読み出し増幅が大幅に導入されている。 Bloomフィルタのような補助構造は役に立つが、ツリーの深さとデータセットサイズでスケールするメモリコストを課す。 学習データ構造の最近の進歩は、機械学習モデルがこれらのコンポーネントを拡張したり置き換えたりすることを示唆し、データ適応的な振る舞いのために手作りのヒューリスティックを取引している。 本研究では,学習した予測をLSMツリーのルックアップパスに統合するための2つのアプローチについて検討する。 ひとつは分類器を使用してブルームフィルタプローブを無関係なレベルに選択的にバイパスし、平均的なクエリ待ち時間を短縮する。 2つ目は、Bloomフィルタをコンパクトな学習モデルと小さなバックアップフィルタに置き換え、正確性を損なうことなくメモリフットプリントの削減を狙う。 モンキースタイルのLSMツリー上に、レベル付きコンパクト化、レベルごとのブルームフィルタ、現実的なワークロードを備えた両方のメソッドを実装します。 実験の結果,Bloomフィルタチェックの30%以上を高い精度でスキップすることで,GET遅延を最大2.28倍まで低減できることがわかった。 学習したブルームフィルタの設計は、ゼロの偽陰性を実現し、メモリ使用量を70～80%削減しながらベースラインレイテンシを保持する。 これらの設計は、レイテンシ、メモリ、正しさの相補的なトレードオフを示し、書き込み最適化ストレージシステムにおける学習されたインデックスコンポーネントの可能性を強調している。

関連論文リスト

• Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection [12.555117983678624]
  これらの問題に対処するために,カスケード学習ブルームフィルタ (CLBF) を提案する。 動的プログラミングに基づく最適化は、モデルとフィルタサイズの間の最適なバランスを実現する構成を自動的に選択する。 実世界のデータセットでの実験では、CLBFは最先端のBloomフィルタと比較してメモリ使用量を最大24%削減し、リジェクション時間を最大14倍削減している。
  論文  参考訳（メタデータ） (2025-02-06T01:05:41Z)
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  本研究では,プルーンドモデルの損失を最適化することにより,確率空間におけるプルーニングマスクを直接学習する最適化に基づく構造的プルーニングを提案する。 我々は、基底となるベルヌーイ分布をサンプルのバイナリ・プルーニングマスクに学習することでこれを実現する。 LLaMA, LLaMA-2, LLaMA-3, Vicuna, Mistral モデルによる実験により, 本手法の有効性と有効性を示すことができた。
  論文  参考訳（メタデータ） (2024-06-15T09:31:03Z)
• Characterizing the Accuracy -- Efficiency Trade-off of Low-rank Decomposition in Language Models [1.401463252785724]
  低ランクの分解は、大規模にリアルタイムサービスを必要とするLLMベースのアプリケーションにとって有望な方向である。 低ランクな分解設計空間を形式化し、分解設計空間が巨大であることを示す。 以上の結果から,最小精度で9%のモデルサイズ削減を達成できることが示唆された。
  論文  参考訳（メタデータ） (2024-05-10T17:40:02Z)
• Filter Pruning for Efficient CNNs via Knowledge-driven Differential Filter Sampler [103.97487121678276]
  フィルタプルーニングは同時に計算を加速し、CNNのメモリオーバーヘッドを低減する。 本稿では,MFM(Masked Filter Modeling)フレームワークを用いた知識駆動型微分フィルタサンプリング(KDFS)を提案する。
  論文  参考訳（メタデータ） (2023-07-01T02:28:41Z)
• Learning Large-scale Neural Fields via Context Pruned Meta-Learning [60.93679437452872]
  本稿では,大規模ニューラルネットワーク学習のための最適化に基づくメタラーニング手法を提案する。 メタテスト時間における勾配再スケーリングは、非常に高品質なニューラルネットワークの学習を可能にすることを示す。 我々のフレームワークは、モデルに依存しない、直感的で、実装が容易であり、幅広い信号に対する大幅な再構成改善を示す。
  論文  参考訳（メタデータ） (2023-02-01T17:32:16Z)
• A Critical Analysis of Classifier Selection in Learned Bloom Filters [0.3359875577705538]
  フィルタ構築に使用されるデータの"複雑さ"は、そのパフォーマンスに大きく影響する可能性がある。 本稿では,学習ブルームフィルタの設計,解析,実装のための新しい手法を提案する。 提案手法とサポートソフトウェアは有効かつ有用であることを示す実験結果が得られた。
  論文  参考訳（メタデータ） (2022-11-28T17:17:18Z)
• Unrolled Compressed Blind-Deconvolution [77.88847247301682]
  sparse multi channel blind deconvolution (S-MBD) はレーダー/ソナー/超音波イメージングなどの多くの工学的応用で頻繁に発生する。 そこで本研究では,受信した全信号に対して,はるかに少ない測定値からブラインドリカバリを可能にする圧縮手法を提案する。
  論文  参考訳（メタデータ） (2022-09-28T15:16:58Z)
• Compressing (Multidimensional) Learned Bloom Filters [7.6058140480517356]
  Bloomフィルタは、要素が基礎となる集合に含まれていないか、あるいは特定のエラー率に含まれていないかを明らかにする。 ディープラーニングモデルは、このメンバシップテストの問題を解決するために使用される。 学習したブルームフィルタの利点は、膨大なデータを考慮する場合にのみ明らかである。
  論文  参考訳（メタデータ） (2022-08-05T07:54:48Z)
• Symbolic Learning to Optimize: Towards Interpretability and Scalability [113.23813868412954]
  近年のL2O(Learning to Optimize)研究は,複雑なタスクに対する最適化手順の自動化と高速化に期待できる道のりを示唆している。 既存のL2Oモデルは、ニューラルネットワークによる最適化ルールをパラメータ化し、メタトレーニングを通じてそれらの数値ルールを学ぶ。 本稿では,L2Oの総合的な記号表現と解析の枠組みを確立する。 そこで本稿では,大規模問題にメタトレーニングを施す軽量なL2Oモデルを提案する。
  論文  参考訳（メタデータ） (2022-03-13T06:04:25Z)

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

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