論文の概要: CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs
- arxiv url: http://arxiv.org/abs/2308.15136v2
- Date: Tue, 9 Jul 2024 02:41:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-11 00:31:04.058393
- Title: CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs
- Title(参考訳): CAGRA:GPUの並列グラフ構築と近似近傍探索
- Authors: Hiroyuki Ootomo, Akira Naruse, Corey Nolet, Ray Wang, Tamas Feher, Yong Wang,
- Abstract要約: 本稿では,並列計算ハードウェアを用いた近接グラフと探索アルゴリズムを提案する。
現代のハードウェアの高性能機能を活用することで,本手法は顕著な効率向上を実現している。
90%から95%のリコール範囲での大規模クエリスループットでは,HNSWよりも3377倍高速で,GPUのSOTA実装よりも3.88.8倍高速である。
- 参考スコア(独自算出の注目度): 4.55224304015001
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Approximate Nearest Neighbor Search (ANNS) plays a critical role in various disciplines spanning data mining and artificial intelligence, from information retrieval and computer vision to natural language processing and recommender systems. Data volumes have soared in recent years and the computational cost of an exhaustive exact nearest neighbor search is often prohibitive, necessitating the adoption of approximate techniques. The balanced performance and recall of graph-based approaches have more recently garnered significant attention in ANNS algorithms, however, only a few studies have explored harnessing the power of GPUs and multi-core processors despite the widespread use of massively parallel and general-purpose computing. To bridge this gap, we introduce a novel parallel computing hardware-based proximity graph and search algorithm. By leveraging the high-performance capabilities of modern hardware, our approach achieves remarkable efficiency gains. In particular, our method surpasses existing CPU and GPU-based methods in constructing the proximity graph, demonstrating higher throughput in both large- and small-batch searches while maintaining compatible accuracy. In graph construction time, our method, CAGRA, is 2.2~27x faster than HNSW, which is one of the CPU SOTA implementations. In large-batch query throughput in the 90% to 95% recall range, our method is 33~77x faster than HNSW, and is 3.8~8.8x faster than the SOTA implementations for GPU. For a single query, our method is 3.4~53x faster than HNSW at 95% recall.
- Abstract(参考訳): 近似Nearest Neighbor Search(ANNS)は、情報検索やコンピュータビジョンから自然言語処理、レコメンダシステムまで、データマイニングと人工知能にまたがる様々な分野において重要な役割を果たす。
近年,データ量の増加が進み,近接探索の計算コストの増大がしばしば禁止され,近似手法の採用が求められている。
グラフベースのアプローチのバランスの取れた性能とリコールは、ANNSアルゴリズムにおいて近年大きな注目を集めているが、大規模並列および汎用コンピューティングが広く使われているにもかかわらず、GPUとマルチコアプロセッサのパワーを活用する研究はごくわずかである。
このギャップを埋めるために,並列計算ハードウェアを用いた近接グラフと探索アルゴリズムを導入する。
現代のハードウェアの高性能機能を活用することで,本手法は顕著な効率向上を実現している。
特に,提案手法は,近接グラフ構築における既存のCPUおよびGPUベースの手法を超越し,大小両方の探索において高いスループットを示すとともに,精度の両立を図っている。
グラフ構築時間において,提案手法であるCAGRAは,CPU SOTA実装の一つであるHNSWよりも2.2~27倍高速である。
90%から95%のリコール範囲における大規模クエリスループットでは,HNSWよりも33~77倍,GPUのSOTA実装より3.8~8.8倍高速である。
単一のクエリでは、HNSWよりも95%リコールで3.4~53倍高速である。
関連論文リスト
- Implementation and Analysis of GPU Algorithms for Vecchia Approximation [0.8057006406834466]
Vecchia Approximationは計算複雑性を減らすために広く使われており、恥ずかしい並列アルゴリズムで計算することができる。
Vecchia Approximationのためにマルチコアソフトウェアが開発されたが、グラフィックス処理ユニット(GPU)上で動作するように設計されたソフトウェアは不足している。
我々の新しい手法は他の2つより優れており、GpGpU Rパッケージに表示されます。
論文 参考訳(メタデータ) (2024-07-03T01:24:44Z) - INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order
Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
計算グラフとして表される関数を考えると、従来のアーキテクチャはn階勾配を効率的に計算する上で困難に直面している。
InR-Archは,n階勾配の計算グラフをハードウェア最適化データフローアーキテクチャに変換するフレームワークである。
1.8-4.8x と 1.5-3.6x の高速化を CPU と GPU のベースラインと比較した結果を示す。
論文 参考訳(メタデータ) (2023-08-11T04:24:39Z) - ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate
Nearest Neighbor Search Algorithms [5.478671305092084]
本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。
我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
論文 参考訳(メタデータ) (2023-05-07T19:28:23Z) - 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) - Towards making the most of NLP-based device mapping optimization for
OpenCL kernels [5.6596607119831575]
我々は、加速されたOpenCLカーネルのための最適なデバイス選択(CPUまたはGPU)の問題に取り組むCummins et al.、すなわちDeeptuneの開発を拡張した。
ソースコードの文脈情報を拡張した4つの異なるモデルを提案する。
実験の結果,提案手法はCumminsらの手法を上回り,予測精度を最大4%向上させることがわかった。
論文 参考訳(メタデータ) (2022-08-30T10:20:55Z) - FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor
Search [20.928821121591493]
効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。
FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。
実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
論文 参考訳(メタデータ) (2022-06-22T22:30:46Z) - Providing Meaningful Data Summarizations Using Examplar-based Clustering
in Industry 4.0 [67.80123919697971]
我々は,従来のCPUアルゴリズムと比較して,一精度で最大72倍,半精度で最大452倍の高速化を実現していることを示す。
提案アルゴリズムは射出成形プロセスから得られた実世界のデータに適用し, 得られたサマリーが, コスト削減と不良部品製造の削減のために, この特定のプロセスのステアリングにどのように役立つかについて議論する。
論文 参考訳(メタデータ) (2021-05-25T15:55:14Z) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳(メタデータ) (2021-03-17T23:13:25Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳(メタデータ) (2020-06-18T08:16:25Z) - Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
ヘテロジニアスCPU+GPUアーキテクチャの深層学習のためのトレーニングアルゴリズムについて検討する。
私たちの2倍の目標 -- 収束率と資源利用を同時に最大化する -- は、この問題を難しくします。
これらのアルゴリズムの実装は,複数の実データセットよりも高速な収束と資源利用の両立を実現していることを示す。
論文 参考訳(メタデータ) (2020-04-19T05:21:20Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳(メタデータ) (2020-04-16T16:20:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。