論文の概要: Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
- arxiv url: http://arxiv.org/abs/2405.18680v3
- Date: Thu, 24 Oct 2024 20:21:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-28 13:33:16.329021
- Title: Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
- Title（参考訳）: 高次元近傍探索のためのナビゲート可能なグラフ:構築と限界
- Authors: Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, Torsten Suel,
- Abstract要約: グラフが任意の開始ノードから任意のターゲットノードへの移動に成功すれば、グラフはナビゲート可能である。
アプリケーションにとって重要な問題は、スペーサーグラフを構築することができるかどうかである。
任意の次元において、任意の距離関数に対して、平均次数$O(sqrtn log n )$の任意の$n$点に対してナビゲート可能なグラフを構築するための単純かつ効率的な方法を与える。
- 参考スコア（独自算出の注目度）: 24.592554830963966
- License:
- Abstract: There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of navigable graphs over high-dimensional point sets. A graph is navigable if we can successfully move from any starting node to any target node using a greedy routing strategy where we always move to the neighbor that is closest to the destination according to a given distance function. The complete graph is navigable for any point set, but the important question for applications is if sparser graphs can be constructed. While this question is fairly well understood in low-dimensions, we establish some of the first upper and lower bounds for high-dimensional point sets. First, we give a simple and efficient way to construct a navigable graph with average degree $O(\sqrt{n \log n })$ for any set of $n$ points, in any dimension, for any distance function. We compliment this result with a nearly matching lower bound: even under the Euclidean metric in $O(\log n)$ dimensions, a random point set has no navigable graph with average degree $O(n^{\alpha})$ for any $\alpha < 1/2$. Our lower bound relies on sharp anti-concentration bounds for binomial random variables, which we use to show that the near-neighborhoods of a set of random points do not overlap significantly, forcing any navigable graph to have many edges.
- Abstract（参考訳）: 近年,グラフに基づく近接探索手法への関心が高まっており,その多くが高次元点集合上のナビゲート可能なグラフの構築に重点を置いている。
グラフは、任意の開始ノードから任意の目標ノードへ、所定の距離関数に従って目的地に最も近い隣人へ常に移動する、欲求ルーティング戦略を用いて、うまく移動することができればナビゲート可能である。
完全なグラフは任意の点集合に対してナビゲート可能であるが、アプリケーションにとって重要な問題はスペーサーグラフを構築することができるかどうかである。
この問題は低次元においてかなりよく理解されているが、高次元の点集合に対する最初の上界と下界のいくつかを確立する。
まず、任意の次元の任意の$n$点に対して平均次数$O(\sqrt{n \log n })$のナビゲート可能なグラフを構築するための単純かつ効率的な方法を与える。
ユークリッド計量の$O(\log n)$次元の下でも、任意の$\alpha < 1/2$に対して平均級数$O(n^{\alpha})$のナビゲート可能なグラフが存在しない。
我々の下界は二項確率変数の鋭い反集中境界に依存しており、これはランダムな点の集合の近傍が著しく重複しないことを示すために使われる。
関連論文リスト
- Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。
この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。
我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-02-27T18:12:58Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
論文 参考訳（メタデータ） (2021-07-29T20:37:28Z) - 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) - Topology-Aware Graph Pooling Networks [51.9008939769679]
ポーリング操作はコンピュータビジョンや自然言語処理タスクに有効である。
グラフデータ上でプーリング操作を実行する上での課題のひとつは、グラフ上で明確に定義されていない局所性の欠如である。
本稿では,グラフトポロジを明示的に考慮したトポロジ対応プーリング(TAP)層を提案する。
論文 参考訳（メタデータ） (2020-10-19T20:14:30Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis [7.99536002595393]
本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。
モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
論文 参考訳（メタデータ） (2020-04-30T12:31:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。