論文の概要: SPFresh: Incremental In-Place Update for Billion-Scale Vector Search

• arxiv url: http://arxiv.org/abs/2410.14452v1
• Date: Fri, 18 Oct 2024 13:24:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 12:31:00.000835
• Title: SPFresh: Incremental In-Place Update for Billion-Scale Vector Search
• Title（参考訳）: SPFresh: 数十億ドル規模のベクター検索のためのインプレッションアップデート
• Authors: Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, Mao Yang,
• Abstract要約: 位置ベクトル更新をサポートするシステムであるSPFreshを紹介する。 SPFreshの中心は軽量なインクリメンタルリバランシングプロトコルであるLIREである。 LIREでは,グローバルリビルドに基づくソリューションに対して,クエリレイテンシと精度が向上する。
• 参考スコア（独自算出の注目度）: 19.245438083030006
• License:
• Abstract: Approximate Nearest Neighbor Search (ANNS) is now widely used in various applications, ranging from information retrieval, question answering, and recommendation, to search for similar high-dimensional vectors. As the amount of vector data grows continuously, it becomes important to support updates to vector index, the enabling technique that allows for efficient and accurate ANNS on vectors. Because of the curse of high dimensionality, it is often costly to identify the right neighbors of a single new vector, a necessary process for index update. To amortize update costs, existing systems maintain a secondary index to accumulate updates, which are merged by the main index by global rebuilding the entire index periodically. However, this approach has high fluctuations of search latency and accuracy, not even to mention that it requires substantial resources and is extremely time-consuming for rebuilds. We introduce SPFresh, a system that supports in-place vector updates. At the heart of SPFresh is LIRE, a lightweight incremental rebalancing protocol to split vector partitions and reassign vectors in the nearby partitions to adapt to data distribution shift. LIRE achieves low-overhead vector updates by only reassigning vectors at the boundary between partitions, where in a high-quality vector index the amount of such vectors are deemed small. With LIRE, SPFresh provides superior query latency and accuracy to solutions based on global rebuild, with only 1% of DRAM and less than 10% cores needed at the peak compared to the state-of-the-art, in a billion scale vector index with 1% of daily vector update rate.
• Abstract（参考訳）: 近似Nearest Neighbor Search (ANNS) は、情報検索、質問応答、レコメンデーションから、同様の高次元ベクトルの探索まで、様々な用途で広く使われている。 ベクターデータの量が継続的に増加するにつれて、ベクター上で効率よく正確なANNSを可能にする技術であるベクターインデックスの更新をサポートすることが重要になる。 高次元の呪いのため、インデックス更新に必要な1つの新しいベクトルの正しい隣人を特定するのに、しばしばコストがかかる。 更新コストを抑えるため、既存のシステムは2次インデックスを維持して更新を蓄積し、そのインデックス全体を定期的にグローバルに再構築することでメインインデックスにマージする。 しかし,本手法は検索待ち時間や精度の変動が大きいため,かなりのリソースが必要であり,再構築には非常に時間がかかることも言うまでもない。 位置ベクトル更新をサポートするシステムであるSPFreshを紹介する。 SPFreshの中心となるのは、ベクトルパーティションと近傍のパーティション内のベクトルを分割してデータ分散シフトに対応するための軽量なインクリメンタルリバランシングプロトコルであるLIREである。 LIREは分割の境界でのみベクトルを再割り当てすることで低オーバーヘッドベクトル更新を達成し、高品質なベクトルインデックスではそのようなベクトルの量は小さいと見なされる。 LIREを使用すると、SPFreshはグローバルリビルドに基づくソリューションに優れたクエリレイテンシと精度を提供し、DRAMの1%に過ぎず、ピーク時に必要となるコアは10%以下である。

関連論文リスト

• GleanVec: Accelerating vector search with minimalist nonlinear dimensionality reduction [1.1599570446840546]
  クロスモーダル検索(例えば、画像を見つけるためにテキストクエリを使用する)は急速に勢いを増している。 クエリはデータベースベクトルとは異なる統計分布を持つことが多いため、高い精度を達成することは困難である。 本稿では,高次元ベクトル探索を高速化するために,次元削減のための線形非線形手法を提案する。
  論文  参考訳（メタデータ） (2024-10-14T21:14:27Z)
• 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)
• Locally-Adaptive Quantization for Streaming Vector Search [1.151101202055732]
  高効率ベクトル圧縮法であるLocally-Adaptive Vector Quantization (LVQ)は、非進化データベースに対して最先端の探索性能を得る。 LVQの2つの改善点として,Turbo LVQとMulti-means LVQを導入し,検索性能を28%,27%向上させた。 我々の研究は、LVQとその新しい変種が高速ベクトル探索を可能にし、同じ分散データに対して、最も近い競合である9.4倍の性能を発揮することを示した。
  論文  参考訳（メタデータ） (2024-02-03T05:43:39Z)
• The Faiss library [54.589857872477445]
  Faissは、インデックス化手法と関連するプリミティブのツールキットで、ベクトルの検索、クラスタ化、圧縮、変換に使用される。 本稿では,ベクトル探索のトレードオフ空間とFaissの設計原理について,構造,最適化,インターフェースの観点から述べる。
  論文  参考訳（メタデータ） (2024-01-16T11:12:36Z)
• LeanVec: Searching vectors faster by making them fit [1.0863382547662974]
  本稿では,高次元ベクトル上での類似性探索を高速化するために,線形次元減少とベクトル量子化を組み合わせたフレームワークLeanVecを提案する。 LeanVecは、検索のスループットを最大3.7倍改善し、インデックスビルド時間を最大4.9倍高速化する、最先端の結果を生成する。
  論文  参考訳（メタデータ） (2023-12-26T21:14:59Z)
• Similarity search in the blink of an eye with compressed indices [3.39271933237479]
  グラフベースのインデックスは現在、数十億の類似性検索において、最高のパフォーマンス技術である。 より高速でより小さなグラフベースのインデックスを作成するための新しい手法とシステムを提案する。
  論文  参考訳（メタデータ） (2023-04-07T23:10:39Z)
• Improving Out-of-Distribution Generalization of Neural Rerankers with Contextualized Late Interaction [52.63663547523033]
  マルチベクトルの最も単純な形式である後期相互作用は、[]ベクトルのみを使用して類似度スコアを計算する神経リランカにも役立ちます。 異なるモデルサイズと多様な性質の第一段階のレトリバーに一貫性があることが示される。
  論文  参考訳（メタデータ） (2023-02-13T18:42:17Z)
• CITADEL: Conditional Token Interaction via Dynamic Lexical Routing for Efficient and Effective Multi-Vector Retrieval [72.90850213615427]
  マルチベクター検索法はスパース(例えばBM25)と高密度(例えばDPR)レトリバーの利点を組み合わせたものである。 これらの手法は桁違いに遅く、単ベクトルの手法に比べてインデックスを格納するのにはるかに多くのスペースを必要とする。 動的語彙ルーティング(CITADEL)による条件付きトークンの相互作用を,効率的かつ効率的なマルチベクタ検索のために提案する。
  論文  参考訳（メタデータ） (2022-11-18T18:27:35Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)

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

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