論文の概要: Graph-based Nearest Neighbors with Dynamic Updates via Random Walks

• arxiv url: http://arxiv.org/abs/2512.18060v1
• Date: Fri, 19 Dec 2025 21:00:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-23 18:54:32.171671
• Title: Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
• Title（参考訳）: ランダムウォークによる動的更新によるグラフベース最近傍地区
• Authors: Nina Mishra, Yonatan Naamad, Tal Wagner, Lichen Zhang,
• Abstract要約: ランダムウォークに基づくグラフベース近似近傍探索(ANN)のための新しい理論的枠組みを提案する。 次に、このフレームワークを用いて、点を削除する前に、グラフと比較してヒット時間統計を保存するランダム化された削除アプローチを分析する。 大規模な実験を通じて、クエリ待ち時間、リコール、削除時間、メモリ使用量とのトレードオフを改善できることが示されています。
• 参考スコア（独自算出の注目度）: 14.905912653448686
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Approximate nearest neighbor search (ANN) is a common way to retrieve relevant search results, especially now in the context of large language models and retrieval augmented generation. One of the most widely used algorithms for ANN is based on constructing a multi-layer graph over the dataset, called the Hierarchical Navigable Small World (HNSW). While this algorithm supports insertion of new data, it does not support deletion of existing data. Moreover, deletion algorithms described by prior work come at the cost of increased query latency, decreased recall, or prolonged deletion time. In this paper, we propose a new theoretical framework for graph-based ANN based on random walks. We then utilize this framework to analyze a randomized deletion approach that preserves hitting time statistics compared to the graph before deleting the point. We then turn this theoretical framework into a deterministic deletion algorithm, and show that it provides better tradeoff between query latency, recall, deletion time, and memory usage through an extensive collection of experiments.
• Abstract（参考訳）: 近似近傍探索(ANN)は、特に大規模言語モデルや検索拡張生成の文脈において、関連する検索結果を検索する一般的な方法である。 ANNの最も広く使われているアルゴリズムの1つは、階層ナビゲート可能な小型世界(Hierarchical Navigable Small World, HNSW)と呼ばれるデータセット上に多層グラフを構築することに基づいている。 このアルゴリズムは新しいデータの挿入をサポートしているが、既存のデータの削除はサポートしていない。 さらに、前処理で記述された削除アルゴリズムは、クエリ待ち時間の増加、リコールの削減、削除時間の延長といったコストがかかる。 本稿では,ランダムウォークに基づくグラフベースANNの理論的枠組みを提案する。 次に、このフレームワークを用いて、点を削除する前に、グラフと比較してヒット時間統計を保存するランダム化された削除アプローチを分析する。 次に、この理論的フレームワークを決定論的削除アルゴリズムに変換し、広範囲な実験の収集を通じて、クエリレイテンシ、リコール、削除時間、メモリ使用量とのトレードオフを改善できることを示します。

関連論文リスト

• In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search [12.092920351505036]
  IP-DiskANNは,挿入処理と削除処理を効率よく行うことにより,バッチ統合を回避する最初のアルゴリズムである。 ハイリコールとローリコールの両方で、様々な長い更新パターンに対して安定したリコールを行う。
  論文  参考訳（メタデータ） (2025-02-19T15:41:08Z)
• LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search [4.194768796374315]
  本稿では,内積近似が多出力回帰問題であることを示す観測に基づく新しい教師付きスコア計算法を提案する。 実験の結果,提案手法はクエリ待ち時間とメモリ使用量の両方においてPQよりも優れていることがわかった。 また,クラスタリングに基づくANNライブラリであるLoRANNを導入する。
  論文  参考訳（メタデータ） (2024-10-24T17:13:39Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。 鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。 このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
  論文  参考訳（メタデータ） (2022-11-22T10:18:33Z)
• 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)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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