論文の概要: On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search

• arxiv url: http://arxiv.org/abs/2610.38133v1
• Date: Wed, 28 Oct 2026 01:14:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.355277
• Title: On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
• Title（参考訳）: グラフベース近辺探索における最悪条件保証について
• Abstract要約: ユークリッド空間に近接する近傍探索に対して,標準的なグラフベースの手法ではサブ線形クエリ時間を実現できないことを示す。 一方,探索グラフのスタイナー点を許容すれば,サブ線形クエリ時間が可能であることを証明した。
• 参考スコア（独自算出の注目度）: 26.83255198721074
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}(n^{1/(c-1)})$. We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods.
• Abstract（参考訳）: HNSW, DiskANN, NSGなどのグラフベースの近接探索アルゴリズムは,IVFデータ構造や局所感性ハッシュ(Locality Sensitive Hashing, LSH)のような空間分割手法と比較して,優れた経験的性能のため,近年人気が高まっている。 しかし、LSHや関連する手法とは対照的に、グラフに基づく探索の最悪の理論的保証を得ることは困難であることが証明されている。 本稿では,そのような保証に対する進展の欠如を説明する上で有効な,強い下限を証明する。 平面グラフや階層グラフ上でグリーディ探索の変種を実行するような)標準グラフベースの手法では、任意に大きい近似係数であっても、ユークリッド空間に近接する近傍探索に対してサブ線形クエリ時間を達成することができないことを示す。 一方,探索グラフのスタイナー点を許容すれば,サブ線形クエリ時間が可能であることを証明した。 我々は LSH に匹敵するバウンダリを取得し、例えば、Steiner 点を用いたグラフベースの探索は、クエリ時間 $\tilde{O}(n^{1/(c-1)})$ でユークリッド空間における近似近傍探索を$c$$で解くことができることを示す。 この結果は、スタイナー点を実践的なグラフベースの手法に組み込む方法についての最初の実験で補完する。

関連論文リスト

• Efficiently Constructing Sparse Navigable Graphs [15.180901064191575]
  グラフベースの近接検索手法は近年人気が高まっており、様々なアプリケーションで最先端のパフォーマンスを提供している。 これらの手法の中心は、距離関数を持つ与えられたデータセットに対して、スパースナビゲート可能な探索グラフを構築するタスクである。 本研究では,探索グラフ構築のための証明可能な保証付き高速アルゴリズムの研究を開始する。
  論文  参考訳（メタデータ） (2025-07-17T17:04:18Z)
• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations [20.944914202453962]
  グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。 本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
  論文  参考訳（メタデータ） (2023-10-29T19:25:48Z)
• 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)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  行動認識に基づく新規性探索(BR-NS)という,新規性推定の代替手法について議論する。 BR-NSはアーカイブを必要とせず、行動空間で定義できるメトリクスを前提にせず、近隣の検索に依存しません。 我々は、その実現可能性とダイナミクス、および時間複雑性の観点からアーカイブベースのnsよりも潜在的に有利な点について洞察を得るために実験を行う。
  論文  参考訳（メタデータ） (2021-04-08T17:31:34Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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