論文の概要: Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search

• arxiv url: http://arxiv.org/abs/2610.37176v1
• Date: Tue, 27 Oct 2026 13:02:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-28 21:04:31.630674
• Title: Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search
• Title（参考訳）: 効率的な近似近傍探索のための近接グラフ指数の無損失圧縮
• Abstract要約: グラフベースの近似Nearest Neighbor(ANN)インデックスは、現代のベクトル検索のバックボーンである。 その巨大なメモリフットプリントは、インフラストラクチャの深刻なボトルネックを生み出します。 本稿では,ライブHNSWルーティングに適した圧縮手法を提案する。
• 参考スコア（独自算出の注目度）: 8.912762581732132
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph-based Approximate Nearest Neighbor (ANN) indexes, such as HNSW, are the backbone of modern vector search. However, their massive memory footprint creates a severe infrastructure bottleneck. While vector quantization is widely adopted to reduce the memory required to store data vectors, the graph's edge structure increasingly dominates total memory usage. Compressing these adjacency lists for online search presents a critical system challenge: because decompression occurs during query processing, i.e., while navigating the graph, memory savings cannot come at the expense of query latency. In this paper, we present a compression technique explicitly tailored for live HNSW routing. By applying offline graph permutations to artificially induce structural locality, we enable the use of SIMD-accelerated integer compressors, such as Stream VByte, for rapid on-the-fly decompression. Evaluated across diverse real-world workloads, we significantly outperform the current state of the art in both compression ratio and query latency. Our experimental results show that we achieve compression ratios up to 52.7% with negligible penalties in latency compared to the uncompressed baseline. Furthermore, our technique has been effectively deployed in production at eBay, achieving up to 44.3% reduction in edge storage with no degradation in query latency.
• Abstract（参考訳）: HNSWのようなグラフベースの近似Nearest Neighbor(ANN)インデックスは、現代のベクトル探索のバックボーンである。 しかし、その巨大なメモリフットプリントは、深刻なインフラストラクチャボトルネックを生み出します。 ベクトル量子化はデータベクトルを保存するのに必要なメモリを減らすために広く採用されているが、グラフのエッジ構造はメモリ全体の使用量を支配している。 クエリ処理中に減圧が発生するため、例えば、グラフをナビゲートしている間は、メモリの節約はクエリのレイテンシを犠牲にすることはできない。 本稿では,ライブHNSWルーティングに適した圧縮手法を提案する。 人工的に構造的局所性を誘導するためにオフライングラフの置換を適用することにより,ストリームVByteなどのSIMD加速型整数圧縮機を高速なオンザフライ圧縮に利用することができる。 さまざまな実世界のワークロードで評価され、圧縮率とクエリレイテンシの両方において、現在の最先端よりも大幅に優れています。 実験の結果,圧縮率を52.7%まで向上し,非圧縮ベースラインと比較して遅延の無視可能なペナルティを達成できた。 さらに、当社のテクニックはeBayで運用に効果的にデプロイされており、クエリレイテンシの低下を伴わずに、最大44.3%のエッジストレージの削減を実現している。

関連論文リスト

• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  SSR(Single-stage Sparse Retrieval)は、高価なクラスタリングを効率的なスパースコーディングに置き換えるパラダイムシフトである。 ColBERTv2と比較してインデックス処理時間を15倍短縮し、検索レイテンシを半減させ、同時に検索性能を向上させる。
  論文  参考訳（メタデータ） (2026-05-28T15:53:34Z)
• Prompt Compression in the Wild: Measuring Latency, Rate Adherence, and Quality for Faster LLM Inference [5.608398371429037]
  LLMLinguaは、プロンプト長、圧縮比、ハードウェア容量がよく一致した場合、最大18%のエンドツーエンドのスピードアップを達成する。 効率的な圧縮は、ワークロードをデータセンターGPUからコモディティカードにオフロードするのに十分なメモリ使用量を削減できることを示す。
  論文  参考訳（メタデータ） (2026-04-03T11:41:53Z)
• Forward Index Compression for Learned Sparse Retrieval [15.629655228398567]
  我々は、全てのアルゴリズム的なフレーバーに共通するデータ構造のサイズに焦点を合わせ、インデックス全体のサイズであるフォワードインデックスのかなりの部分を構成する。 特に,検索品質や内部積計算のレイテンシを損なうことなく,フォワードインデックスのストレージフットプリントを削減する圧縮手法を提案する。
  論文  参考訳（メタデータ） (2026-02-05T08:35:17Z)
• ChunkKV: Semantic-Preserving KV Cache Compression for Efficient Long-Context LLM Inference [61.412894960600205]
  大きな言語モデル(LLM)は、長いテキストを処理する際に大きなGPUメモリを必要とする。 ChunkKVは、セマンティックチャンクを基本的な圧縮単位として扱うことで、KVキャッシュ圧縮を再定義する。 結果: ChunkKVは最先端の手法を最大8.7%精度で上回る。
  論文  参考訳（メタデータ） (2025-02-01T03:49:47Z)
• Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search [11.938555573590964]
  インデックスのサイズを減らすために、ロスシー圧縮が広く適用されている。 逆ファイルとグラフベースのインデックスでは、ベクトルIDやリンクなどの補助データはほとんどのストレージコストを表すことができる。 いくつかのデータセットに対して、これらの手法は量子化されたベクトルコードも無害に圧縮できることを示す。
  論文  参考訳（メタデータ） (2025-01-16T20:45:11Z)
• Fast Feedforward 3D Gaussian Splatting Compression [55.149325473447384]
  3D Gaussian Splatting (FCGS) は、1つのフィードフォワードパスで3DGS表現を高速に圧縮できる最適化フリーモデルである。 FCGSは圧縮比を20倍以上に向上し、高精細度を維持しながら、ほとんどのシーン毎のSOTA最適化手法を上回ります。
  論文  参考訳（メタデータ） (2024-10-10T15:13:08Z)
• Similarity search in the blink of an eye with compressed indices [3.39271933237479]
  グラフベースのインデックスは現在、数十億の類似性検索において、最高のパフォーマンス技術である。 より高速でより小さなグラフベースのインデックスを作成するための新しい手法とシステムを提案する。
  論文  参考訳（メタデータ） (2023-04-07T23:10:39Z)

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

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