論文の概要: Efficiently Constructing Sparse Navigable Graphs
- arxiv url: http://arxiv.org/abs/2507.13296v1
- Date: Thu, 17 Jul 2025 17:04:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-18 20:10:24.587098
- Title: Efficiently Constructing Sparse Navigable Graphs
- Title（参考訳）: スパースナビゲーション可能なグラフを効率的に構築する
- Authors: Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Rob Johnson, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen,
- Abstract要約: 我々は任意の距離関数の下で$O(log n)$-approximate sparsest navigable graphを構築するための$tildeO(n2)$ timeアルゴリズムを提案する。
また、本手法は、$alpha$-shortcut reachable と $tau$-monotonic graph を構築する際に、密接に関連し、実質的に重要な問題に対して立方体時間を超えることができることを示す。
- 参考スコア（独自算出の注目度）: 11.317292211864013
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph-based nearest neighbor search methods have seen a surge of popularity in recent years, offering state-of-the-art performance across a wide variety of applications. Central to these methods is the task of constructing a sparse navigable search graph for a given dataset endowed with a distance function. Unfortunately, doing so is computationally expensive, so heuristics are universally used in practice. In this work, we initiate the study of fast algorithms with provable guarantees for search graph construction. For a dataset with $n$ data points, the problem of constructing an optimally sparse navigable graph can be framed as $n$ separate but highly correlated minimum set cover instances. This yields a naive $O(n^3)$ time greedy algorithm that returns a navigable graph whose sparsity is at most $O(\log n)$ higher than optimal. We improve significantly on this baseline, taking advantage of correlation between the set cover instances to leverage techniques from streaming and sublinear-time set cover algorithms. Combined with problem-specific pre-processing techniques, we present an $\tilde{O}(n^2)$ time algorithm for constructing an $O(\log n)$-approximate sparsest navigable graph under any distance function. The runtime of our method is optimal up to logarithmic factors under the Strong Exponential Time Hypothesis via a reduction from Monochromatic Closest Pair. Moreover, we prove that, as with general set cover, obtaining better than an $O(\log n)$-approximation is NP-hard, despite the significant additional structure present in the navigable graph problem. Finally, we show that our techniques can also beat cubic time for the closely related and practically important problems of constructing $\alpha$-shortcut reachable and $\tau$-monotonic graphs, which are also used for nearest neighbor search. For such graphs, we obtain $\tilde{O}(n^{2.5})$ time or better algorithms.
- Abstract（参考訳）: グラフベースの近接検索手法は近年人気が高まっており、様々なアプリケーションで最先端のパフォーマンスを提供している。
これらの手法の中心は、距離関数を持つ与えられたデータセットに対して、スパースナビゲート可能な探索グラフを構築するタスクである。
残念ながら、そのような処理は計算に高価であるため、ヒューリスティックスは実際は普遍的に使われている。
本研究では,探索グラフ構築のための証明可能な保証付き高速アルゴリズムの研究を開始する。
n$のデータポイントを持つデータセットの場合、最適にスパースなナビゲート可能なグラフを構築するという問題は、$n$で分離されるが、非常に相関性の高い最小セットカバーインスタンスとしてフレーム化できる。
これにより、単純な$O(n^3)$ time greedyアルゴリズムが得られ、このアルゴリズムは、空白が最大で$O(\log n)$以上のナビゲート可能なグラフを返す。
我々は,このベースラインを改良し,セットカバーインスタンス間の相関を利用して,ストリーミングとサブラインタイムのセットカバーアルゴリズムの手法を活用する。
問題固有の事前処理手法と組み合わせて、任意の距離関数の下で$O(\log n)$-approximate sparsest navigable graphを構築するための$\tilde{O}(n^2)$ timeアルゴリズムを提案する。
本手法のランタイムは,単色クローズトペアの低減によるStrong Exponential Time仮説の下での対数係数に最適である。
さらに、一般集合被覆と同様に、ナビゲートグラフ問題に有意な付加構造が存在するにもかかわらず、$O(\log n)$-近似がNPハードであることを証明する。
最後に, 近接探索にも用いられる, $\alpha$-shortcut reachable と $\tau$-monotonic graph を構築することによる, 密接に関連し, 事実上重要な問題に対して, この手法が立方体時間を上回ることを示す。
そのようなグラフに対して、 $\tilde{O}(n^{2.5})$ time or better algorithm を得る。
関連論文リスト
- Incremental Approximate Single-Source Shortest Paths with Predictions [10.749658550545238]
インクリメンタルグラフにおける最短経路を近似的に維持する基本データ構造問題について検討する。
これらのテクニックは、直ちに全ペアの最短パス設定にも拡張されます。
私たちのアルゴリズムは、予測がほぼ完璧である場合(オフラインアルゴリズムとほぼ同等の速さで実行される)一貫性があります。
論文 参考訳（メタデータ） (2025-02-12T05:06:23Z) - Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits [24.592554830963966]
グラフが任意の開始ノードから任意のターゲットノードへの移動に成功すれば、グラフはナビゲート可能である。
アプリケーションにとって重要な問題は、スペーサーグラフを構築することができるかどうかである。
任意の次元において、任意の距離関数に対して、平均次数$O(sqrtn log n )$の任意の$n$点に対してナビゲート可能なグラフを構築するための単純かつ効率的な方法を与える。
論文 参考訳（メタデータ） (2024-05-29T01:07:26Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - 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) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文 参考訳（メタデータ） (2021-06-10T09:29:05Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文 参考訳（メタデータ） (2020-02-05T16:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。