論文の概要: RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search

• arxiv url: http://arxiv.org/abs/2601.07183v1
• Date: Mon, 12 Jan 2026 04:05:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:01.204098
• Title: RAIRS: Optimizing Redundant Assignment and List Layout for IVF-Based ANN Search
• Title（参考訳）: RAIRS:IVFベースのANN検索のための冗長割り当てとリストレイアウトの最適化
• Authors: Zehai Yang, Shimin Chen,
• Abstract要約: IVFは、ベクトルデータベースにおいて最も広く使われているANNS(Approximate Nearest Neighbors Search)手法の1つである。 データベクトルとリストセントロイド間の距離に基づいて第2のIVFリストを選択するナイーブ戦略は、性能が良くない。 本稿では、共有セルを利用したIVF検索の繰り返し距離計算を行うための最適化されたリストレイアウトであるRAIRSを提案する。
• 参考スコア（独自算出の注目度）: 2.3923661696583545
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: IVF is one of the most widely used ANNS (Approximate Nearest Neighbors Search) methods in vector databases. The idea of redundant assignment is to assign a data vector to more than one IVF lists for reducing the chance of missing true neighbors in IVF search. However, the naive strategy, which selects the second IVF list based on the distance between a data vector and the list centroids, performs poorly. Previous work focuses only on the inner product distance, while there is no optimized list selection study for the most popular Euclidean space. Moreover, the IVF search may access the same vector in more than one lists, resulting in redundant distance computation and decreasing query throughput. In this paper, we present RAIRS to address the above two challenges. For the challenge of the list selection, we propose an optimized AIR metric for the Euclidean space. AIR takes not only distances but also directions into consideration in order to support queries that are closer to the data vector but father away from the first chosen list's centroid. For the challenge of redundant distance computation, we propose SEIL, an optimized list layout that exploits shared cells to reduce repeated distance computations for IVF search. Our experimental results using representative real-world data sets show that RAIRS out-performs existing redundant assignment solutions and achieves up to 1.33x improvement over the best-performing IVF method, IVF-PQ Fast Scan with refinement.
• Abstract（参考訳）: IVFは、ベクトルデータベースにおいて最も広く使われているANNS(Approximate Nearest Neighbors Search)手法の1つである。 冗長代入の考え方は、データベクトルを複数のIVFリストに割り当てることによって、IVF検索で真の隣人が行方不明になる可能性を減らすことである。 しかし、データベクトルとリストセントロイド間の距離に基づいて第2のIVFリストを選択するナイーブ戦略は、性能が良くない。 これまでの研究は、内積距離のみに焦点を当てていたが、最も人気のあるユークリッド空間に対する最適化されたリスト選択研究は存在しない。 さらに、IVF検索は複数のリストで同じベクトルにアクセスすることができ、冗長な距離計算とクエリスループットの低下をもたらす。 本稿では,上記の2つの課題に対処するためにRAIRSを提案する。 リスト選択の課題として,ユークリッド空間に最適化されたAIRメトリックを提案する。 AIRは距離だけでなく、データベクトルに近いクエリをサポートするために考慮すべき方向も考慮します。 冗長距離計算の課題として,共有セルを利用したIVF検索における繰り返し距離計算の削減のための最適化されたリストレイアウトSEILを提案する。 代表的な実世界のデータセットを用いた実験結果から、RAIRSは既存の冗長代入ソリューションより優れており、最高のIVF法であるIVF-PQ高速スキャンよりも最大1.33倍向上していることがわかった。

関連論文リスト

• NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance [7.108581652658526]
  グラフ(GDBMS)のネイティブベクトルインデックスであるNaviXを提示する。 NaviXは階層的ナビゲート可能な小型世界(HNSW)グラフ上に構築されている。
  論文  参考訳（メタデータ） (2025-06-29T21:16:07Z)
• Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search [14.77572360618428]
  高次元近似$K$近接探索(AKNN)は情報検索を含む様々なアプリケーションの基本課題である。 AKNNの既存のアルゴリズムのほとんどは、候補生成と距離比較演算(DCO)という2つの主要コンポーネントに分解することができる。 低次元空間における正確な距離を近似するDADEと呼ばれるデータ認識距離推定手法を提案する。
  論文  参考訳（メタデータ） (2024-11-26T08:51:46Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
  論文  参考訳（メタデータ） (2023-05-04T17:01:17Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  本稿では,クロスエンコーダのみに頼って,二重エンコーダによる検索を回避する手法を提案する。 我々のアプローチは、現在の広く使われている方法よりも優れたテスト時間リコール-vs計算コストトレードオフを提供する。
  論文  参考訳（メタデータ） (2022-10-23T00:32:04Z)
• Electra: Conditional Generative Model based Predicate-Aware Query Approximation [10.056919500568013]
  ELECTRAは述語対応のAQPシステムで、多くの述語で分析スタイルのクエリに答えることができ、近似誤差ははるかに小さい。 実世界の3つのデータセットに対する4つの異なるベースラインによる評価の結果,ELECTRAはベースラインと比較して多数の述語に対して低いAQP誤差を提供することがわかった。
  論文  参考訳（メタデータ） (2022-01-28T21:13:26Z)
• Highly Parallel Autoregressive Entity Linking with Discriminative Correction [51.947280241185]
  自己回帰リンクを全ての潜在的な言及に対して並列化する,非常に効率的な手法を提案する。 我々のモデルは以前の生成法より70倍高速で精度が高い。
  論文  参考訳（メタデータ） (2021-09-08T17:28:26Z)
• VSAC: Efficient and Accurate Estimator for H and F [68.65610177368617]
  VSACはRANSAC型頑健な推定器であり、多くの新奇性がある。 従来のすべてのプロセッサよりも大幅に高速で、CPU上では平均1-2msで動作する。 現在最も正確な2次元幾何学推定器である MAGSAC++ と同等の精度で2桁高速である。
  論文  参考訳（メタデータ） (2021-06-18T17:04:57Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。 本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
  論文  参考訳（メタデータ） (2020-04-30T18:09:50Z)
• Inverted-File k-Means Clustering: Performance Analysis [1.3955252961896318]
  inverted-file k-means clustering algorithm (IVF) は、潜在的に多数のクラスを持つ大規模なスパースデータセットに適したアルゴリズムである。 我々は,IVFが設計アルゴリズムよりも優れた性能を実現することを実験的に実証した。
  論文  参考訳（メタデータ） (2020-02-21T02:20:33Z)

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

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