論文の概要: 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倍のメモリを削減した。
関連論文リスト
- 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) - 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) - FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor
Search [20.928821121591493]
効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。
FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。
実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
論文 参考訳(メタデータ) (2022-06-22T22:30:46Z) - Variable Bitrate Neural Fields [75.24672452527795]
本稿では,特徴格子を圧縮し,メモリ消費を最大100倍に削減する辞書手法を提案する。
辞書の最適化をベクトル量子化オートデコーダ問題として定式化し、直接監督できない空間において、エンドツーエンドの離散神経表現を学習する。
論文 参考訳(メタデータ) (2022-06-15T17:58:34Z) - Augmenting Novelty Search with a Surrogate Model to Engineer
Meta-Diversity in Ensembles of Classifiers [5.8497361730688695]
行動多様性を促進するために神経進化とノベルティ検索を組み合わせることで、分類のための高性能なアンサンブルを構築することができる。
本稿では,2つのニューラルネットワークアーキテクチャ間の挙動距離を推定する代理モデルを用いて,この制限を克服する手法を提案する。
論文 参考訳(メタデータ) (2022-01-30T19:13:32Z) - 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) - Fast, Compact and Highly Scalable Visual Place Recognition through
Sequence-based Matching of Overloaded Representations [33.50309671827902]
我々は、非常に大規模な1000万の場所データセットにおいて、いかに効果的に場所認識率が達成できるかを示す。
我々は、非常に大規模な1000万の場所データセットにおいて、いかに効果的に場所認識率が達成できるかを示す。
論文 参考訳(メタデータ) (2020-01-23T10:31:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。