論文の概要: Fast Single-Core K-Nearest Neighbor Graph Computation

• arxiv url: http://arxiv.org/abs/2112.06630v1
• Date: Mon, 13 Dec 2021 13:16:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-14 22:20:34.058413
• Title: Fast Single-Core K-Nearest Neighbor Graph Computation
• Title（参考訳）: 高速シングルコアK-Nearest近辺グラフ計算
• Authors: Dan Kluser, Jonas Bokstaller, Samuel Rutz and Tobias Buner
• Abstract要約: 本論文では,Wei Dongらによるランタイム"NN-Descent"アルゴリズムを最適化したC実装を提案する。 低次元および高次元データセットの性能を改善するための様々な実装最適化について説明する。 l2距離メートル法の制限により、高次元データセットの性能を大幅に向上させるブロックされた距離評価が利用可能となる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fast and reliable K-Nearest Neighbor Graph algorithms are more important than ever due to their widespread use in many data processing techniques. This paper presents a runtime optimized C implementation of the heuristic "NN-Descent" algorithm by Wei Dong et al. for the l2-distance metric. Various implementation optimizations are explained which improve performance for low-dimensional as well as high dimensional datasets. Optimizations to speed up the selection of which datapoint pairs to evaluate the distance for are primarily impactful for low-dimensional datasets. A heuristic which exploits the iterative nature of NN-Descent to reorder data in memory is presented which enables better use of locality and thereby improves the runtime. The restriction to the l2-distance metric allows for the use of blocked distance evaluations which significantly increase performance for high dimensional datasets. In combination the optimizations yield an implementation which significantly outperforms a widely used implementation of NN-Descent on all considered datasets. For instance, the runtime on the popular MNIST handwritten digits dataset is halved.
• Abstract（参考訳）: 高速で信頼性の高いK-Nearest Neighbor Graphアルゴリズムは、多くのデータ処理技術で広く使われているため、これまで以上に重要である。 本稿では,Wei DongらによるL2距離検定のためのヒューリスティックNN-Descentアルゴリズムのランタイム最適化C実装を提案する。 低次元および高次元データセットのパフォーマンスを改善する様々な実装最適化について説明する。 距離を評価するためのデータポイントペアの選択を高速化する最適化は、主に低次元データセットに影響を及ぼす。 NN-Descentの反復的な性質を利用してメモリ内のデータを並べ替えることにより、局所性を向上し、ランタイムを改善する。 l2距離メトリックへの制限により、高次元データセットのパフォーマンスを大幅に向上させるブロック距離評価が利用可能となる。 組み合わせて最適化することで、すべての考慮されたデータセット上で広く使われているNN-Descentの実装を著しく上回る実装が得られる。 例えば、人気のあるMNIST手書き桁データセットのランタイムは半減である。

関連論文リスト

• Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation [20.409659920455955]
  近似k-Nearest Neighbour (ANN) 法は情報マイニングや大規模高次元データセットでの機械学習支援によく用いられる。 静的なデータセットを持つアプリケーションでは、ランタイム制約とデータセットプロパティを使用して、適切な操作特性を持つANNメソッドを経験的に選択することができる。 従来の評価手法は、インデックス構造を更新する際の計算コストや、インデックス更新の率とサイズを考慮していない。
  論文  参考訳（メタデータ） (2024-04-30T06:21:44Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• Improved Distribution Matching for Dataset Condensation [91.55972945798531]
  本稿では,分布マッチングに基づく新しいデータセット凝縮法を提案する。 提案手法は,計算資源の少ない従来の最適化指向手法よりも優れている。
  論文  参考訳（メタデータ） (2023-07-19T04:07:33Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Alternately Optimized Graph Neural Networks [33.98939289745346]
  グラフ上の半教師付き学習のための新しい最適化フレームワークを提案する。 提案手法は交互最適化アルゴリズムにより便利に解けるので,効率は大幅に向上する。
  論文  参考訳（メタデータ） (2022-06-08T01:50:08Z)
• Efficient Wind Speed Nowcasting with GPU-Accelerated Nearest Neighbors Algorithm [0.0]
  本稿では, 簡易かつ効率的な高高度風速流路を提案する。 空域全体にわたって航空機が記録した大量のライブデータを効率的に処理する。 データセットの各ポイントごとにユニークなコンテキストを生成し、そこから外挿する。
  論文  参考訳（メタデータ） (2021-12-20T09:15:27Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  完全接続型ReLUネットワークのニューラルタンジェントカーネル(NTK)の効率的な特徴マップ構築を提案する。 得られた特徴の次元は、理論と実践の両方で比較誤差境界を達成するために、他のベースライン特徴マップ構造よりもはるかに小さいことを示しています。
  論文  参考訳（メタデータ） (2021-04-03T09:08:12Z)
• Analytical Characterization and Design Space Exploration for Optimization of CNNs [10.15406080228806]
  ループタイルやループ置換を含むループレベルの最適化は、データ移動を減らすための基本的な変換です。 本稿では,マルチコアCPU上でのCNNの最適ループレベル最適化構成を求めるための解析モデルを提案する。
  論文  参考訳（メタデータ） (2021-01-24T21:36:52Z)
• Population Gradients improve performance across data-sets and architectures in object classification [6.17047113475566]
  ニューラルネットワーク(NN)の学習中に勾配を計算する新しい手法を提案する。 アーキテクチャ、データセット、ハイパーパラメータ値、トレーニング長、モデルサイズにわたる最終的なパフォーマンスを大幅に改善する。 私たちがテストした広範囲な状況において有効であるのに加えて、パフォーマンスの向上(例えば、F1)は他の広範なパフォーマンス改善手法のどれよりも高いか高いかのどちらかです。
  論文  参考訳（メタデータ） (2020-10-23T09:40:23Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)

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

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