論文の概要: Fast Exact Retrieval for Nearest-neighbor Lookup (FERN)

• arxiv url: http://arxiv.org/abs/2405.04435v1
• Date: Tue, 7 May 2024 15:57:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-08 13:31:20.802727
• Title: Fast Exact Retrieval for Nearest-neighbor Lookup (FERN)
• Title（参考訳）: 近近縁ルックアップ(FERN)における高速エクササイズ検索
• Authors: Richard Zhu,
• Abstract要約: 厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 近距離近傍探索(FERN)のための対数的高速エクササイズ検索のための新しいアルゴリズムを提案する。 このアルゴリズムは1000万ドルの$d=128$に対して100%リコールした$O(dlog N)$ルックアップを達成する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exact nearest neighbor search is a computationally intensive process, and even its simpler sibling -- vector retrieval -- can be computationally complex. This is exacerbated when retrieving vectors which have high-dimension $d$ relative to the number of vectors, $N$, in the database. Exact nearest neighbor retrieval has been generally acknowledged to be a $O(Nd)$ problem with no sub-linear solutions. Attention has instead shifted towards Approximate Nearest-Neighbor (ANN) retrieval techniques, many of which have sub-linear or even logarithmic time complexities. However, if our intuition from binary search problems (e.g. $d=1$ vector retrieval) carries, there ought to be a way to retrieve an organized representation of vectors without brute-forcing our way to a solution. For low dimension (e.g. $d=2$ or $d=3$ cases), \texttt{kd-trees} provide a $O(d\log N)$ algorithm for retrieval. Unfortunately the algorithm deteriorates rapidly to a $O(dN)$ solution at high dimensions (e.g. $k=128$), in practice. We propose a novel algorithm for logarithmic Fast Exact Retrieval for Nearest-neighbor lookup (FERN), inspired by \texttt{kd-trees}. The algorithm achieves $O(d\log N)$ look-up with 100\% recall on 10 million $d=128$ uniformly randomly generated vectors.\footnote{Code available at https://github.com/RichardZhu123/ferns}
• Abstract（参考訳）: 厳密な近接探索は計算集約的なプロセスであり、より単純なシブリング(ベクトル探索)さえも計算的に複雑である。 これは、データベース内のベクトル数に対して高次元の$d$を持つベクトルを検索する場合、さらに悪化する。 厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 注意は代わりにANN(Adroximate Nearest-Neighbor)検索技術に移行し、その多くはサブ線形あるいは対数的時間的複雑さを持つ。 しかし、二項探索問題(例えば$d=1$ベクトル探索)からの直観が通るなら、解への道を強要することなく、ベクトルの整理された表現を回収する方法があるはずだ。 低次元(例: $d=2$ または $d=3$ の場合)に対して、 \texttt{kd-trees} は検索のための$O(d\log N)$アルゴリズムを提供する。 残念ながらアルゴリズムは急速に劣化し、実際には高次元の$O(dN)$解(例えば$k=128$)になる。 そこで本研究では,近近辺探索(FERN)のための対数的高速実行検索のための新しいアルゴリズムを提案し,そのアルゴリズムを‘texttt{kd-trees} にインスパイアした。 このアルゴリズムは1000万ドルの$d=128$に対して100\%のリコールで$O(d\log N)$ルックアップを達成する。 \footnote{Code available at https://github.com/RichardZhu123/ferns}

関連論文リスト

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• A Query-Optimal Algorithm for Finding Counterfactuals [14.934032347716995]
  我々は,その性能に関する理論的保証が強い反事実を見つけるアルゴリズムを設計する。 [ S(f)O(Delta_f(xstar))cdot log d]クエリを$f$にし、xstar$でslの最適カウンターファクトを返します。
  論文  参考訳（メタデータ） (2022-07-14T17:21:13Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Well Separated Pair Decomposition and power weighted shortest path metric algorithm fusion [0.0]
  私たちは、あるポイントセットで$s$-wellの分離ペアを$mathbbrn$, $n$$$>$$1で計算するアルゴリズムを考えています。 また、ダイクストラのアルゴリズムの置換であるアルゴリズムについても検討し、特定のパワー重み付き最短経路メトリックを用いてk$-nearestの隣人を計算し、$mathbbrn$,$n$$$$$$$$$$で計算する。
  論文  参考訳（メタデータ） (2021-03-20T17:38:13Z)
• Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
  木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。 Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。 本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-08-01T14:21:45Z)
• Quantum algorithms for graph problems with cut queries [17.149741568581096]
  量子アルゴリズムは、$O(d log(n)2) の後に最大$d$のグラフを学習できることを示す。 また、量子アルゴリズムは、$O(sqrtm log(n)3/2)$多くのカットクエリで一般的なグラフを学習できることを示す。
  論文  参考訳（メタデータ） (2020-07-16T12:21:01Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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