論文の概要: Quake: Adaptive Indexing for Vector Search

• arxiv url: http://arxiv.org/abs/2506.03437v2
• Date: Fri, 06 Jun 2025 19:58:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 11:53:35.398838
• Title: Quake: Adaptive Indexing for Vector Search
• Title（参考訳）: Quake: ベクトル検索のための適応インデックス作成
• Authors: Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F. Ilyas, Theodoros Rekatsinas, Shivaram Venkataraman,
• Abstract要約: 動的環境において低レイテンシと高リコールを維持する適応インデックスシステムであるQuakeを導入する。 評価の結果、動的ワークロードでは、Quakeは1.5-38xのクエリレイテンシ削減と4.5-126xの更新レイテンシ削減を実現している。
• 参考スコア（独自算出の注目度）: 9.530779665725715
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Vector search, the task of finding the k-nearest neighbors of a query vector against a database of high-dimensional vectors, underpins many machine learning applications, including retrieval-augmented generation, recommendation systems, and information retrieval. However, existing approximate nearest neighbor (ANN) methods perform poorly under dynamic and skewed workloads where data distributions evolve. We introduce Quake, an adaptive indexing system that maintains low latency and high recall in such environments. Quake employs a multi-level partitioning scheme that adjusts to updates and changing access patterns, guided by a cost model that predicts query latency based on partition sizes and access frequencies. Quake also dynamically sets query execution parameters to meet recall targets using a novel recall estimation model. Furthermore, Quake utilizes NUMA-aware intra-query parallelism for improved memory bandwidth utilization during search. To evaluate Quake, we prepare a Wikipedia vector search workload and develop a workload generator to create vector search workloads with configurable access patterns. Our evaluation shows that on dynamic workloads, Quake achieves query latency reductions of 1.5-38x and update latency reductions of 4.5-126x compared to state-of-the-art indexes such as SVS, DiskANN, HNSW, and SCANN.
• Abstract（参考訳）: ベクトル探索は、高次元ベクトルのデータベースに対してクエリベクトルのk-nearest隣人を見つけるタスクであり、検索強化生成、レコメンデーションシステム、情報検索を含む多くの機械学習アプリケーションを支える。 しかし、データ分散が進化する動的および歪んだワークロード下では、既存の近接隣り合う(ANN)手法は不十分である。 このような環境で低レイテンシと高リコールを維持する適応型インデックスシステムであるQuakeを紹介する。 Quakeでは、更新とアクセスパターンの変更を調整するマルチレベルパーティショニングスキームを採用しており、パーティショニングサイズとアクセス頻度に基づいてクエリレイテンシを予測するコストモデルによってガイドされている。 Quakeはまた、新しいリコール推定モデルを使用してリコールターゲットを満たすためにクエリ実行パラメータを動的に設定する。 さらに、QuakeはNUMA対応のクエリ内並列処理を利用して、検索時のメモリ帯域幅利用を改善する。 Quakeを評価するために、ウィキペディアのベクトル検索ワークロードを作成し、構成可能なアクセスパターンを持つベクトル検索ワークロードを生成するワークロードジェネレータを開発する。 評価の結果,動的ワークロードでは,SVS,DiskANN,HNSW,SCANNなどの最先端インデックスと比較してクエリレイテンシの1.5-38x,更新レイテンシの4.5-126xを実現している。

関連論文リスト

• vCache: Verified Semantic Prompt Caching [75.87215136638828]
  本稿では,ユーザ定義エラー率保証を備えた最初の検証済みセマンティックキャッシュであるvCacheを提案する。 オンライン学習アルゴリズムを使用して、キャッシュされたプロンプト毎に最適な閾値を推定し、追加のトレーニングなしで信頼性の高いキャッシュ応答を可能にする。 我々の実験によると、vCacheは特定のエラー境界を一貫して満たし、最先端の静的な閾値と微調整された埋め込みベースラインより優れています。
  論文  参考訳（メタデータ） (2025-02-06T04:16:20Z)
• 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)
• Similarity search in the blink of an eye with compressed indices [3.39271933237479]
  グラフベースのインデックスは現在、数十億の類似性検索において、最高のパフォーマンス技術である。 より高速でより小さなグラフベースのインデックスを作成するための新しい手法とシステムを提案する。
  論文  参考訳（メタデータ） (2023-04-07T23:10:39Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。 近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。 我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
  論文  参考訳（メタデータ） (2021-12-13T13:49:11Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)
• MS-RANAS: Multi-Scale Resource-Aware Neural Architecture Search [94.80212602202518]
  我々は,MS-RANAS(Multi-Scale Resource-Aware Neural Architecture Search)を提案する。 我々は,検索コストの削減を図るために,ワンショットのアーキテクチャ探索手法を採用した。 我々は精度-速度トレードオフの観点から最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-09-29T11:56:01Z)
• Latency-Aware Differentiable Neural Architecture Search [113.35689580508343]
  近年、探索コストの低さと検索空間設計の柔軟性から、微分可能なニューラルネットワーク探索法が人気を博している。 しかし、これらの手法はネットワーク最適化の難しさに悩まされており、検索されたネットワークはハードウェアに不便な場合が多い。 本稿では,この問題を最適化に微分可能な遅延損失項を追加することにより,精度とレイテンシのトレードオフをバランス係数で行うことができる。
  論文  参考訳（メタデータ） (2020-01-17T15:55:21Z)

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

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