論文の概要: Similarity search in the blink of an eye with compressed indices
- arxiv url: http://arxiv.org/abs/2304.04759v2
- Date: Mon, 24 Jul 2023 18:10:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-26 21:02:57.128136
- Title: Similarity search in the blink of an eye with compressed indices
- Title(参考訳): 圧縮指数を用いた眼の瞬目における類似性探索
- Authors: Cecilia Aguerrebere, Ishwar Bhati, Mark Hildebrand, Mariano Tepper,
Ted Willke
- Abstract要約: グラフベースのインデックスは現在、数十億の類似性検索において、最高のパフォーマンス技術である。
より高速でより小さなグラフベースのインデックスを作成するための新しい手法とシステムを提案する。
- 参考スコア(独自算出の注目度): 3.39271933237479
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Nowadays, data is represented by vectors. Retrieving those vectors, among
millions and billions, that are similar to a given query is a ubiquitous
problem, known as similarity search, of relevance for a wide range of
applications. Graph-based indices are currently the best performing techniques
for billion-scale similarity search. However, their random-access memory
pattern presents challenges to realize their full potential. In this work, we
present new techniques and systems for creating faster and smaller graph-based
indices. To this end, we introduce a novel vector compression method,
Locally-adaptive Vector Quantization (LVQ), that uses per-vector scaling and
scalar quantization to improve search performance with fast similarity
computations and a reduced effective bandwidth, while decreasing memory
footprint and barely impacting accuracy. LVQ, when combined with a new
high-performance computing system for graph-based similarity search,
establishes the new state of the art in terms of performance and memory
footprint. For billions of vectors, LVQ outcompetes the second-best
alternatives: (1) in the low-memory regime, by up to 20.7x in throughput with
up to a 3x memory footprint reduction, and (2) in the high-throughput regime by
5.8x with 1.4x less memory.
- Abstract(参考訳): 現在、データはベクトルで表現されている。
与えられたクエリに類似した数百万から数十億のベクトルを検索することは、さまざまなアプリケーションに関連する類似性検索として知られるユビキタスな問題である。
グラフベースのインデックスは、現在10億規模の類似性検索で最高のパフォーマンス技術である。
しかし、ランダムアクセスメモリパターンは、その潜在能力をフルに実現するための課題を提示する。
本稿では,より高速で小さなグラフベースのインデックスを作成するための新しい手法とシステムを提案する。
そこで本研究では,ベクトル毎のスケーリングとスカラー量子化を用いて,メモリフットプリントの削減と精度の低下を図りながら,高速な類似性計算と有効帯域幅の削減により探索性能を向上させるベクトル圧縮手法LVQを提案する。
lvqはグラフベースの類似性検索のための新しい高性能コンピューティングシステムと組み合わせて、パフォーマンスとメモリフットプリントの観点から新しい最先端を確立する。
数十億のベクトルに対して、LVQは、(1)低メモリで最大20.7倍のスループットで最大3倍のメモリフットプリントを削減し、(2)高スループットで5.8倍のメモリを削減した。
関連論文リスト
- Adaptive Semantic Prompt Caching with VectorQ [78.59891542553179]
ベクトル類似度メトリクスは、キャッシュ内の埋め込みプロンプトと最も近い隣人の類似度を定量化するために数値スコアを割り当てる。
この1つの大きさの閾値は、異なるプロンプトで不十分であることを示す。
埋め込みの複雑さと不確実性に適応する埋め込み固有のしきい値領域を学習するためのフレームワークであるVectorQを提案する。
論文 参考訳(メタデータ) (2025-02-06T04:16:20Z) - Efficient and Effective Retrieval of Dense-Sparse Hybrid Vectors using Graph-based Approximate Nearest Neighbor Search [14.821492155733555]
グラフに基づく高密度疎ハイブリッドベクトルのためのANNSアルゴリズムを提案する。
提案アルゴリズムは,既存のハイブリッドベクトル探索アルゴリズムと同等の精度で8.9x$sim$11.7xスループットを実現する。
論文 参考訳(メタデータ) (2024-10-27T09:12:51Z) - 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) - 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) - Compact Neural Graphics Primitives with Learned Hash Probing [100.07267906666293]
学習したプローブを持つハッシュテーブルにはデメリットはなく,その結果,サイズと速度の組合せが好適であることを示す。
推論は、トレーニングが1.2-2.6倍遅い間、同じ品質で未処理のハッシュテーブルよりも高速である。
論文 参考訳(メタデータ) (2023-12-28T18:58:45Z) - LeanVec: Searching vectors faster by making them fit [1.0863382547662974]
本稿では,高次元ベクトル上での類似性探索を高速化するために,線形次元減少とベクトル量子化を組み合わせたフレームワークLeanVecを提案する。
LeanVecは、検索のスループットを最大3.7倍改善し、インデックスビルド時間を最大4.9倍高速化する、最先端の結果を生成する。
論文 参考訳(メタデータ) (2023-12-26T21:14:59Z) - 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) - Variable Bitrate Neural Fields [75.24672452527795]
本稿では,特徴格子を圧縮し,メモリ消費を最大100倍に削減する辞書手法を提案する。
辞書の最適化をベクトル量子化オートデコーダ問題として定式化し、直接監督できない空間において、エンドツーエンドの離散神経表現を学習する。
論文 参考訳(メタデータ) (2022-06-15T17:58:34Z) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳(メタデータ) (2021-03-17T23:13:25Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。