論文の概要: Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2501.10479v1
• Date: Thu, 16 Jan 2025 20:45:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:22:55.540845
• Title: Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search
• Title（参考訳）: 近似近傍探索のためのベクトルIDのロスレス圧縮
• Authors: Daniel Severo, Giuseppe Ottaviano, Matthew Muckley, Karen Ullrich, Matthijs Douze,
• Abstract要約: インデックスのサイズを減らすために、ロスシー圧縮が広く適用されている。 逆ファイルとグラフベースのインデックスでは、ベクトルIDやリンクなどの補助データはほとんどのストレージコストを表すことができる。 いくつかのデータセットに対して、これらの手法は量子化されたベクトルコードも無害に圧縮できることを示す。
• 参考スコア（独自算出の注目度）: 11.938555573590964
• License:
• Abstract: Approximate nearest neighbor search for vectors relies on indexes that are most often accessed from RAM. Therefore, storage is the factor limiting the size of the database that can be served from a machine. Lossy vector compression, i.e., embedding quantization, has been applied extensively to reduce the size of indexes. However, for inverted file and graph-based indices, auxiliary data such as vector ids and links (edges) can represent most of the storage cost. We introduce and evaluate lossless compression schemes for these cases. These approaches are based on asymmetric numeral systems or wavelet trees that exploit the fact that the ordering of ids is irrelevant within the data structures. In some settings, we are able to compress the vector ids by a factor 7, with no impact on accuracy or search runtime. On billion-scale datasets, this results in a reduction of 30% of the index size. Furthermore, we show that for some datasets, these methods can also compress the quantized vector codes losslessly, by exploiting sub-optimalities in the original quantization algorithm. The source code for our approach available at https://github.com/facebookresearch/vector_db_id_compression.
• Abstract（参考訳）: 近接するベクトルの近傍探索は、最も頻繁にRAMからアクセスされるインデックスに依存する。 したがって、ストレージは、マシンから提供可能なデータベースのサイズを制限する要因である。 ロッシーベクトル圧縮(Lossy vector compression、すなわち埋め込み量子化)は、インデックスのサイズを減らすために広く応用されている。 しかし、逆ファイルやグラフベースのインデックスの場合、ベクトルIDやリンク(エッジ)などの補助データはほとんどのストレージコストを表わすことができる。 これらのケースに対して、損失のない圧縮方式を導入し、評価する。 これらのアプローチは、IDの順序がデータ構造の中で無関係であるという事実を利用する非対称な数字系やウェーブレット木に基づいている。 いくつかの設定では、ベクトルIDを第7因子で圧縮することができ、精度や検索ランタイムに影響を与えない。 数十億のデータセットでは、インデックスサイズの30%が削減される。 さらに,これらの手法では,元となる量子化アルゴリズムの準最適性を利用して,量子化されたベクトルコードを無害に圧縮することもできることを示す。 このアプローチのソースコードはhttps://github.com/facebookresearch/vector_db_id_compressionで公開されています。

関連論文リスト

• Generalized compression and compressive search of large datasets [0.0]
  panCAKESは圧縮検索の新しいアプローチであり、圧縮されたデータに対して$k$-NNと$rho$-NN検索を実行する方法である。 PanCAKESは多様体仮説を仮定し、データの低次元構造を利用して効率よく圧縮・探索する。 ゲノミクス、プロテオミクス、データセットなど、さまざまなデータセットでpanCAKESをベンチマークします。
  論文  参考訳（メタデータ） (2024-09-18T17:25:31Z)
• 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)
• Vector search with small radiuses [10.880913075221361]
  本稿では,ベクトル検索結果に応じて難しい決定を下す必要がある場合に着目する。 本研究では,クエリー・ツー・ベクター距離に基づいて,範囲探索結果の値を厳密にモデル化できることを示す。 これにより、範囲探索の指標 RSM が得られ、これは原則的であり、エンドツーエンドの評価を行なわずに計算が容易である。
  論文  参考訳（メタデータ） (2024-03-16T00:34:25Z)
• Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth [83.15263499262824]
  勾配勾配勾配は入力のスパース構造を完全に無視する解に収束することを示す。 浅層構造にデノナイジング関数を付加することにより,スパースデータの圧縮におけるガウス性能の改善方法を示す。 CIFAR-10 や MNIST などの画像データセットに対して,本研究の成果を検証した。
  論文  参考訳（メタデータ） (2024-02-07T16:32:29Z)
• 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)
• Similarity search in the blink of an eye with compressed indices [3.39271933237479]
  グラフベースのインデックスは現在、数十億の類似性検索において、最高のパフォーマンス技術である。 より高速でより小さなグラフベースのインデックスを作成するための新しい手法とシステムを提案する。
  論文  参考訳（メタデータ） (2023-04-07T23:10:39Z)
• Nearest neighbor search with compact codes: A decoder perspective [77.60612610421101]
  バイナリハッシュや製品量化器などの一般的な手法を自動エンコーダとして再解釈する。 後方互換性のあるデコーダを設計し、同じ符号からベクトルの再構成を改善する。
  論文  参考訳（メタデータ） (2021-12-17T15:22:28Z)
• Using Convolutional Neural Networks to Detect Compression Algorithms [0.0]
  ベースデータセットを使用し、さまざまなアルゴリズムですべてのファイルを圧縮し、それに基づいてモデルを設計します。 使用されるモデルは、圧縮、lzip、bzip2を使用して圧縮されたファイルを正確に識別することができた。
  論文  参考訳（メタデータ） (2021-11-17T11:03:16Z)
• Permute, Quantize, and Fine-tune: Efficient Compression of Neural Networks [70.0243910593064]
  ベクトル量子化の成功の鍵は、どのパラメータ群を一緒に圧縮するかを決定することである。 本稿では,隣り合う2つの層の重みを同じ関数を表現しながら不変にすることができることを観察する。 次に、レート歪み理論への接続を確立し、圧縮し易いネットワークとなる置換を探索する。
  論文  参考訳（メタデータ） (2020-10-29T15:47:26Z)
• OctSqueeze: Octree-Structured Entropy Model for LiDAR Compression [77.8842824702423]
  本稿では,LiDAR点雲のメモリフットプリントを削減するための新しいディープ圧縮アルゴリズムを提案する。 本手法は,メモリフットプリントを低減するために,点間の間隔と構造的冗長性を利用する。 我々のアルゴリズムは、自動運転車などのアプリケーションにおいて、LiDARポイントのオンボードおよびオフボードストレージを減らすために使用できる。
  論文  参考訳（メタデータ） (2020-05-14T17:48:49Z)

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

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