論文の概要: In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2502.13826v1
• Date: Wed, 19 Feb 2025 15:41:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-20 13:58:26.868053
• Title: In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search
• Title（参考訳）: 近似近傍探索をストリーミングするグラフインデックスのページ内更新
• Authors: Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, Harsha Vardhan Simhadri,
• Abstract要約: IP-DiskANNは,挿入処理と削除処理を効率よく行うことにより,バッチ統合を回避する最初のアルゴリズムである。 ハイリコールとローリコールの両方で、様々な長い更新パターンに対して安定したリコールを行う。
• 参考スコア（独自算出の注目度）: 12.092920351505036
• License:
• Abstract: Indices for approximate nearest neighbor search (ANNS) are a basic component for information retrieval and widely used in database, search, recommendation and RAG systems. In these scenarios, documents or other objects are inserted into and deleted from the working set at a high rate, requiring a stream of updates to the vector index. Algorithms based on proximity graph indices are the most efficient indices for ANNS, winning many benchmark competitions. However, it is challenging to update such graph index at a high rate, while supporting stable recall after many updates. Since the graph is singly-linked, deletions are hard because there is no fast way to find in-neighbors of a deleted vertex. Therefore, to update the graph, state-of-the-art algorithms such as FreshDiskANN accumulate deletions in a batch and periodically consolidate, removing edges to deleted vertices and modifying the graph to ensure recall stability. In this paper, we present IP-DiskANN (InPlaceUpdate-DiskANN), the first algorithm to avoid batch consolidation by efficiently processing each insertion and deletion in-place. Our experiments using standard benchmarks show that IP-DiskANN has stable recall over various lengthy update patterns in both high-recall and low-recall regimes. Further, its query throughput and update speed are better than using the batch consolidation algorithm and HNSW.
• Abstract（参考訳）: 近接探索(ANNS)の指標は情報検索の基本的な要素であり、データベース、検索、レコメンデーション、RAGシステムで広く使われている。 これらのシナリオでは、ドキュメントや他のオブジェクトが作業セットに挿入され、高速に削除されるため、ベクターインデックスへの更新ストリームが必要になる。 近接グラフ指標に基づくアルゴリズムはANNSにとって最も効率的な指標であり、多くのベンチマーク競争で勝利した。 しかし、多くの更新後に安定したリコールをサポートしながら、そのようなグラフインデックスを高速に更新することは困難である。 グラフは単調にリンクされているので、削除は、削除された頂点の隣側を見つける高速な方法がないため、難しい。 したがって、グラフを更新するために、FreshDiskANNのような最先端のアルゴリズムは、バッチに削除を蓄積し、定期的に統合し、削除された頂点へのエッジを削除し、グラフを変更してリコール安定性を確保する。 本稿では,IP-DiskANN(InPlaceUpdate-DiskANN)を提案する。 標準ベンチマークにより,IP-DiskANNは,ハイリコールと低リコールのいずれにおいても,様々な更新パターンに対して安定したリコールが可能であることを示す。 さらに,クエリスループットと更新速度は,バッチ統合アルゴリズムやHNSWよりも優れている。

関連論文リスト

• SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search [13.349178274732862]
  我々は、量子化とグラフのよりシンフォニーな統合を実現するSymphonyQGを提案する。 実世界のデータセットに関する広範な実験に基づいて、SymphonyQGは、時間精度のトレードオフの観点から、新たな最先端技術を確立している。
  論文  参考訳（メタデータ） (2024-11-19T04:51:08Z)
• Early Exit Strategies for Approximate k-NN Search in Dense Retrieval [10.48678957367324]
  アーリーエグジットのための最先端のA-kNNを構築し,忍耐の概念に基づく教師なし手法を提案する。 我々は,A-kNNの効率を最大5倍の高速化で向上すると同時に,無視可能な効率損失を達成できることを示す。
  論文  参考訳（メタデータ） (2024-08-09T10:17:07Z)
• Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation [0.9592510017131104]
  グラフベースのインデックスは、大量のリアルタイム削除、挿入、更新に直面したとき、受け入れられなくなる。 本稿では,HNSWの欠点を克服するための効率的な対策について述べる。 提案したMN-RUアルゴリズムは,更新効率を効果的に向上し,到達不能な点の成長速度を抑え,全体の性能を向上し,グラフの完全性を維持する。
  論文  参考訳（メタデータ） (2024-07-10T17:37:15Z)
• SOAR: Improved Indexing for Approximate Nearest Neighbor Search [30.752720306189342]
  Orthogonality-Amplified Residuals (SOAR) によるスパイリングは、近接した近傍(ANN)探索のための新しいデータインデックス化手法である。
  論文  参考訳（メタデータ） (2024-03-31T19:09:09Z)
• On Exploring Node-feature and Graph-structure Diversities for Node Drop Graph Pooling [86.65151066870739]
  現在のノードドロッププーリング法は、ノードの特徴やグラフ構造の観点からグラフの多様性を無視し、結果としてグラフレベル以下の表現をもたらす。 そこで本稿では,textiti.fltextbfIpscore と textbfDropscore の2つの操作を持つ textbfMulti スコア空間からなる MID を新たに提案する。 具体的には、多次元スコア空間は、複数の基準を通してノードの重要さを描いており、フリップスコアは異種ノードの維持を奨励している。
  論文  参考訳（メタデータ） (2023-06-22T08:02:01Z)
• Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining [61.09807522366773]
  本稿では,ソフトマックスを証明可能な境界で近似し,木を動的に維持するアルゴリズムを提案する。 我々は,2000万以上のターゲットを持つデータセットについて検討し,オラクル・ブルート力負の鉱業に関して,誤差を半分に削減した。
  論文  参考訳（メタデータ） (2023-03-27T15:18:32Z)
• DSI++: Updating Transformer Memory with New Documents [95.70264288158766]
  DSI++は、DSIが新たなドキュメントをインクリメンタルにインデクシングするための継続的な学習課題である。 新たな文書の連続的な索引付けは,それまでの索引付け文書をかなり忘れてしまうことを示す。 文書の擬似クエリをサンプルとして生成メモリを導入し、連続的なインデックス付け中に補足することで、検索タスクの忘れを防止する。
  論文  参考訳（メタデータ） (2022-12-19T18:59:34Z)
• End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
  Extreme Multi-label Classification (XMC) は現実世界の問題を解決するための一般的なフレームワークである。 本稿では,木系インデックスを特殊重み付きグラフベースインデックスに緩和する新しい手法を提案する。 ELIASは、数百万のラベルを持つ大規模極端分類ベンチマークで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2022-10-16T01:34:17Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  自動回帰言語モデルは、回答を生成するデファクト標準として現れています。 これまでの研究は、探索空間を階層構造に分割する方法を探究してきた。 本研究では,検索空間の任意の構造を強制しない代替として,経路内のすべてのngramを識別子として使用することを提案する。
  論文  参考訳（メタデータ） (2022-04-22T10:45:01Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)

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

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