Fugu-MT 論文翻訳(概要): Graph-Based Nearest-Neighbor Search without the Spread

論文の概要: Graph-Based Nearest-Neighbor Search without the Spread

arxiv url: http://arxiv.org/abs/2602.06633v1
Date: Fri, 06 Feb 2026 11:46:20 GMT
ステータス: 翻訳完了
システム内更新日: 2026-02-10 17:49:39.50572
Title: Graph-Based Nearest-Neighbor Search without the Spread
Title（参考訳）: スプレッドのないグラフベース最近傍探索
Authors: Jeff Giliberti, Sariel Har-Peled, Jonas Sauer, Ali Vakilian,
Abstract要約: 線形サイズグラフと組み合わせて、対数時間でANNクエリに$n$で答えられるような、外部の線形サイズデータ構造を構築する方法を示す。
参考スコア（独自算出の注目度）: 8.868282702497082
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: $\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.
Abstract（参考訳）: $\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct Near-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$。残念ながら、スプレッドは$n$でアンバウンドされるかもしれないし、興味深い理論的疑問はスプレッドへの依存を取り除く方法である。ここでは、線形サイズグラフと組み合わせて、対数時間でANNクエリに$n$で答えられるような、外部の線形サイズデータ構造を構築する方法を示す。

関連論文リスト

On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
論文参考訳（メタデータ） (2026-01-06T18:34:07Z)
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach [37.498311835613045]
最短パス距離計算は、小木幅グラフ上で顕著な効率を達成する。本手法では, 抵抗距離ラベルを$O(n cdot h_mathcalG)$ in $O(n cdot h_mathcalG2 cdot d_max$ とする。我々のラベリングは、$O(h_mathcalG)$時間における正確なシングルペアクエリと$O(n cdot h_mathにおけるシングルソースクエリをサポートします。
論文参考訳（メタデータ） (2025-09-05T14:14:36Z)
Efficiently Constructing Sparse Navigable Graphs [15.180901064191575]
グラフベースの近接検索手法は近年人気が高まっており、様々なアプリケーションで最先端のパフォーマンスを提供している。これらの手法の中心は、距離関数を持つ与えられたデータセットに対して、スパースナビゲート可能な探索グラフを構築するタスクである。本研究では,探索グラフ構築のための証明可能な保証付き高速アルゴリズムの研究を開始する。
論文参考訳（メタデータ） (2025-07-17T17:04:18Z)
Approximating Optimal Labelings for Temporal Connectivity [7.394099294390271]
時間グラフのエッジの可利用時間を、与えられた最大許容時間$a$で全ての頂点が接続されるようにスケジューリングする問題について検討する。この問題は、EmphMinimum Aged Labeling (MAL)として知られるもので、ロジスティクス、流通スケジューリング、ソーシャルネットワークに広がる情報にいくつかの応用がある。
論文参考訳（メタデータ） (2025-04-23T16:00:33Z)
Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。これは密度推定のための新しい統計計算トレードオフである。
論文参考訳（メタデータ） (2024-10-30T15:03:33Z)
Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文参考訳（メタデータ） (2024-08-03T20:08:02Z)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
論文参考訳（メタデータ） (2022-07-15T11:55:09Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Approximating the Log-Partition Function [16.59989033959959]
基礎となるグラフ構造の性質を通じて近似比を定量化する手法を提案する。グラフの有効抵抗を最小に抑えた平方根の逆に等しい近似比を実現するニアリニアタイム変量を提供する。
論文参考訳（メタデータ） (2021-02-19T22:57:32Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)

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