論文の概要: Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory
- arxiv url: http://arxiv.org/abs/2405.03267v2
- Date: Tue, 07 May 2024 10:17:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-11 00:58:45.494702
- Title: Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory
- Title（参考訳）: 数十億規模のベクトル探索における性能のジレンマとインデックスサイズの特徴付けと第2ティアメモリによる破壊
- Authors: Rongxin Cheng, Yifan Peng, Xingda Wei, Hongrui Xie, Rong Chen, Sijie Shen, Haibo Chen,
- Abstract要約: 大規模データセットのベクター検索は、Web検索やRAGのような現代的なオンラインサービスにとって極めて重要である。
既存のSSDベースのグラフとクラスタインデックスのパフォーマンスとインデックスサイズのトレードオフを特徴付ける。
ベクターインデックスは、様々な第2階層メモリデバイスにおいて、桁違いに小さなインデックス増幅で最適な性能が得られることを示す。
- 参考スコア（独自算出の注目度）: 14.432536669959218
- License:
- Abstract: Vector searches on large-scale datasets are critical to modern online services like web search and RAG, which necessity storing the datasets and their index on the secondary storage like SSD. In this paper, we are the first to characterize the trade-off of performance and index size in existing SSD-based graph and cluster indexes: to improve throughput by 5.7$\times$ and 1.7$\times$, these indexes have to pay a 5.8$\times$ storage amplification and 7.7$\times$ with respect to the dataset size, respectively. The root cause is that the coarse-grained access of SSD mismatches the fine-grained random read required by vector indexes with small amplification. This paper argues that second-tier memory, such as remote DRAM/NVM connected via RDMA or CXL, is a powerful storage for addressing the problem from a system's perspective, thanks to its fine-grained access granularity. However, putting existing indexes -- primarily designed for SSD -- directly on second-tier memory cannot fully utilize its power. Meanwhile, second-tier memory still behaves more like storage, so using it as DRAM is also inefficient. To this end, we build a graph and cluster index that centers around the performance features of second-tier memory. With careful execution engine and index layout designs, we show that vector indexes can achieve optimal performance with orders of magnitude smaller index amplification, on a variety of second-tier memory devices. Based on our improved graph and vector indexes on second-tier memory, we further conduct a systematic study between them to facilitate developers choosing the right index for their workloads. Interestingly, the findings on the second-tier memory contradict the ones on SSDs.
- Abstract（参考訳）: 大規模なデータセットのベクトル検索は、Web検索やRAGのような現代的なオンラインサービスにとって非常に重要であり、データセットとそのインデックスをSSDのような二次ストレージに格納する必要がある。
本稿では、既存のSSDベースのグラフとクラスタインデックスのパフォーマンスとインデックスサイズのトレードオフを最初に特徴づける:スループットを5.7$\times$と1.7$\times$で改善するには、データセットサイズに関してそれぞれ5.8$\times$ストレージ増幅と7.7$\times$を支払う必要がある。
根本原因は、SSDの粗い粒度のアクセスが、小増幅のベクトルインデックスが必要とする粒度のランダムな読み取りと一致しないことである。
本稿では、RDMAやCXLを介して接続されたリモートDRAM/NVMのような第2層メモリは、その粒度の細かいアクセスの粒度により、システムの観点からこの問題に対処するための強力なストレージである、と論じる。
しかし、SSD用に主に設計された既存のインデックスを第2階層のメモリに直接配置しても、その電力を十分に利用できない。
一方、第2階層のメモリはストレージのように振る舞うため、DRAMとして使用するのも非効率である。
この目的のために、第2階層メモリの性能特徴を中心に、グラフとクラスタインデックスを構築します。
注意深い実行エンジンとインデックスレイアウト設計により、ベクターインデックスは、様々な第2階層のメモリデバイス上で、桁違いに小さなインデックス増幅で最適な性能を達成できることを示す。
改善したグラフと第2階層メモリ上のベクトルインデックスに基づいて、開発者によるワークロードの適切なインデックス選択を促進するために、それらの間のシステマティックな調査も実施しています。
興味深いことに、第2階層のメモリに関する結果はSSD上のものと矛盾する。
関連論文リスト
- RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval [24.472784635757016]
RetrievalAttentionは、注意計算を高速化し、GPUメモリ消費を減らすためのトレーニング不要のアプローチである。
評価の結果,RetrievalAttentionは高いモデル精度を維持しながら1-3%のデータにのみアクセスする必要があることがわかった。
論文 参考訳（メタデータ） (2024-09-16T17:59:52Z) - 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) - AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval [1.099532646524593]
DiskANNは、RAMとストレージの両方を使用して、大規模データセットのリコール速度バランスを良好に実現している。
製品量子化(PQ)による圧縮ベクターのロードによるメモリ使用量の削減を主張する一方で、そのメモリ使用量はデータセットの規模に比例して増加する。
本稿では、圧縮されたベクトルをストレージにオフロードするAiSAQ(All-in-Storage ANNS with Product Quantization)を提案する。
論文 参考訳（メタデータ） (2024-04-09T04:20:27Z) - ESPN: Memory-Efficient Multi-Vector Information Retrieval [0.36832029288386137]
マルチベクトルモデルは、検索インデックスのメモリとストレージの要求を桁違いに増幅する。
ストレージパイプラインネットワーク(ESPN)からEmbeddingを導入し、再ランクの埋め込みテーブル全体をオフロードして、メモリ要求を5～16倍削減します。
我々は、ヒット率90%を超えるソフトウェアプレフィッシャーを設計し、SSDベースの検索を6.4倍に改善し、大規模なクエリバッチサイズであっても、ほぼメモリレベルのクエリレイテンシを維持できることを実証した。
論文 参考訳（メタデータ） (2023-12-09T00:19:42Z) - Learning to Rank Graph-based Application Objects on Heterogeneous
Memories [0.0]
本稿では,アプリケーションの性能に最も影響を与えるアプリケーションオブジェクトを識別し,特徴付ける手法について述べる。
予測モデルを用いてデータ配置を行うことで,ベースラインのアプローチと比較して,実行時間の劣化を12% (平均) および30% (最大) 削減することができる。
論文 参考訳（メタデータ） (2022-11-04T00:20:31Z) - NumS: Scalable Array Programming for the Cloud [82.827921577004]
タスクベース分散システム上でNumPyのような表現を最適化する配列プログラミングライブラリであるNumSを提案する。
これはLoad Simulated Hierarchical Scheduling (LSHS)と呼ばれる新しいスケジューラによって実現される。
LSHSは、ネットワーク負荷を2倍減らし、メモリを4倍減らし、ロジスティック回帰問題において実行時間を10倍減らし、Rayの性能を向上させる。
論文 参考訳（メタデータ） (2022-06-28T20:13:40Z) - FlashAttention: Fast and Memory-Efficient Exact Attention with
IO-Awareness [80.3586155104237]
FlashAttentionは、トランスフォーマーのためのIO対応の正確な注意アルゴリズムである。
これにより、GPU高帯域メモリ(HBM)とGPUオンチップ間のメモリ読み込み/書き込み数を削減できる。
FlashAttentionとブロックスパース FlashAttentionは、トランスフォーマーのコンテキストを長くすることを可能にする。
論文 参考訳（メタデータ） (2022-05-27T17:53:09Z) - ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and
Gradient Accumulation [106.04777600352743]
微分可能なアーキテクチャサーチ(DARTS)は、スーパーネット全体がメモリに格納されているため、メモリコストが大幅に低下する。
シングルパスのDARTSが登場し、各ステップでシングルパスのサブモデルのみを選択する。
メモリフレンドリーだが、計算コストも低い。
RObustifying Memory-Efficient NAS (ROME) と呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-23T06:34:07Z) - Memformer: A Memory-Augmented Transformer for Sequence Modeling [55.780849185884996]
本稿では、シーケンスモデリングのための効率的なニューラルネットワークであるMemformerを紹介する。
我々のモデルは長いシーケンスを処理する際に線形時間複雑性と一定メモリ空間複雑性を実現する。
論文 参考訳（メタデータ） (2020-10-14T09:03:36Z) - The Case for Learned Spatial Indexes [62.88514422115702]
我々は、空間範囲の問合せに答えるために、最先端の学習した多次元インデックス構造(すなわちFlood)から提案した手法を用いる。
i) パーティション内の機械学習検索は、1次元でフィルタリングを使用する場合の2進探索よりも11.79%速く、39.51%高速であることを示す。
また、2次元でフィルタする最も近い競合相手の1.23倍から1.83倍の速さで機械学習インデックスを精査する。
論文 参考訳（メタデータ） (2020-08-24T12:09:55Z) - Hands-off Model Integration in Spatial Index Structures [8.710716183434918]
本稿では,軽量機械学習モデルを用いて空間インデックスのクエリを高速化する機会について検討する。
我々は、R木において、おそらく最も広く使われている空間指標である、それと類似した手法を使うことの可能性を探ることによって、そうする。
分析で示すように、クエリの実行時間を最大60%削減でき、同時にインデックスのメモリフットプリントを90%以上削減できる。
論文 参考訳（メタデータ） (2020-06-29T22:05:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。