論文の概要: RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search

• arxiv url: http://arxiv.org/abs/2305.18356v1
• Date: Fri, 26 May 2023 17:40:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-31 22:10:12.675437
• Title: RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search
• Title（参考訳）: RT-kNNS Unbound: RT Coresを使って非制限近傍検索を高速化
• Authors: Vani Nagarajan, Durga Mandarapu, Milind Kulkarni
• Abstract要約: RTを高速化した最初の隣接探索であるTrueKNNを提案する。 我々のアプローチは、既存のアプローチよりも桁違いに高速であることを示す。
• 参考スコア（独自算出の注目度）: 0.0764671395172401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of identifying the k-Nearest Neighbors (kNNS) of a point has proven to be very useful both as a standalone application and as a subroutine in larger applications. Given its far-reaching applicability in areas such as machine learning and point clouds, extensive research has gone into leveraging GPU acceleration to solve this problem. Recent work has shown that using Ray Tracing cores in recent GPUs to accelerate kNNS is much more efficient compared to traditional acceleration using shader cores. However, the existing translation of kNNS to a ray tracing problem imposes a constraint on the search space for neighbors. Due to this, we can only use RT cores to accelerate fixed-radius kNNS, which requires the user to set a search radius a priori and hence can miss neighbors. In this work, we propose TrueKNN, the first unbounded RT-accelerated neighbor search. TrueKNN adopts an iterative approach where we incrementally grow the search space until all points have found their k neighbors. We show that our approach is orders of magnitude faster than existing approaches and can even be used to accelerate fixed-radius neighbor searches.
• Abstract（参考訳）: ある点の k-Nearest Neighbors (kNNS) を識別する問題は、スタンドアローンアプリケーションとしても、より大きなアプリケーションではサブルーチンとしても非常に有用であることが証明されている。 機械学習やポイントクラウドなどの分野での広範な適用性を考えると、この問題を解決するためにGPUアクセラレーションを活用するための広範な研究が進められている。 近年の研究では、最近のGPUでRay Tracingコアを使用してkNNSを高速化することが、シェーダコアを使用した従来のアクセラレーションよりもはるかに効率的であることが示されている。 しかし、既存のkNNSのレイトレーシング問題への変換は、近隣の探索空間に制約を課している。 このため、RTコアのみを使用して固定半径kNNSを高速化できるため、ユーザーは検索半径を事前設定する必要があるため、隣人を見逃すことができる。 そこで本研究では,RTをアクセラレーションした最初の非有界近傍探索であるTrueKNNを提案する。 TrueKNNは反復的なアプローチを採用し、すべての点が隣人を見つけるまで、探索空間を漸進的に成長させます。 提案手法は既存手法よりも桁違いに高速であり,固定半径近傍探索の高速化にも有効であることを示す。

関連論文リスト

• Early Exit Strategies for Approximate k-NN Search in Dense Retrieval [10.48678957367324]
  アーリーエグジットのための最先端のA-kNNを構築し,忍耐の概念に基づく教師なし手法を提案する。 我々は,A-kNNの効率を最大5倍の高速化で向上すると同時に,無視可能な効率損失を達成できることを示す。
  論文  参考訳（メタデータ） (2024-08-09T10:17:07Z)
• VN Network: Embedding Newly Emerging Entities with Virtual Neighbors [59.906332784508706]
  本稿では,3つの課題に対処するため,VN(Virtual Neighbor)ネットワークという新しいフレームワークを提案する。 まず、近隣の空間問題を減らすために、ルールによって推測される仮想隣人の概念を導入する。 第二に、複雑なパターンを捉えるために、論理と対称パスのルールの両方を識別する。
  論文  参考訳（メタデータ） (2024-02-21T03:04:34Z)
• Dense Optical Tracking: Connecting the Dots [82.79642869586587]
  DOTは、ビデオにおけるポイントトラッキングの問題を解決するための、新しくてシンプルで効率的な方法である。 OmniMotionのような高度な"ユニバーサルトラッカー"を上回り、CoTrackerのような最良のポイントトラッキングアルゴリズムと同等か、あるいはそれ以上の精度で、DOTが現在の光フロー技術よりもはるかに正確であることを示す。
  論文  参考訳（メタデータ） (2023-12-01T18:59:59Z)
• k-NNN: Nearest Neighbors of Neighbors for Anomaly Detection [20.204147875108976]
  異常検出は、標準から大きく逸脱した画像を特定することを目的としている。 埋め込み空間における特徴の様々な構造と重要性を考慮に入れた新しい演算子を提案する。 既存のアルゴリズムに最も近いコンポーネントをk-NNN演算子に置き換えるだけで、残りのアルゴリズムに手を加えずに、各アルゴリズムの処理結果を改善できることが示される。
  論文  参考訳（メタデータ） (2023-05-28T11:39:51Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
  論文  参考訳（メタデータ） (2023-05-04T17:01:17Z)
• 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)
• Automating Nearest Neighbor Search Configuration with Constrained Optimization [34.633003673080786]
  本研究では、量子化に基づくANNアルゴリズムをチューニングするための制約付き最適化に基づくアプローチを提案する。 提案手法は,所望の検索コストやリコールを入力として処理し,実験的にParetoフロンティアに非常に近いチューニングを生成する。
  論文  参考訳（メタデータ） (2023-01-04T16:56:36Z)
• 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)
• Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms [0.0]
  与えられたクエリポイントのデータセットでk-nearestの隣人を見つける問題は、数年前から解決されてきた。 本稿では,K-Nearest Neighbor Search(K-Nearest Neighbor Search)の手法について,計算の視点から検討する。 本論文では,KNNSアプローチの対敵点に対する堅牢性を評価するために,汎用的な強化学習ベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-02-10T16:10:58Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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