論文の概要: On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU

• arxiv url: http://arxiv.org/abs/2508.15436v1
• Date: Thu, 21 Aug 2025 10:50:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-22 16:26:46.282527
• Title: On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU
• Title（参考訳）: GPUにおける近似近傍探索の高速化におけるグラフ並べ替えの有効性について
• Authors: Yutaro Oguri, Mai Nishimura, Yusuke Matsui,
• Abstract要約: グラフベースの近似Nearest Neighbor Search (ANNS)は、現代のAIアプリケーションにおいて支配的なパラダイムとなっている。 本稿では,GPU上でのグラフベースのANNSに対するグラフの並べ替え効果について,初めて体系的に検討する。
• 参考スコア（独自算出の注目度）: 14.338954144116759
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the first systematic investigation of graph reordering effects for graph-based Approximate Nearest Neighbor Search (ANNS) on a GPU. While graph-based ANNS has become the dominant paradigm for modern AI applications, recent approaches focus on algorithmic innovations while neglecting memory layout considerations that significantly affect execution time. Our unified evaluation framework enables comprehensive evaluation of diverse reordering strategies across different graph indices through a graph adapter that converts arbitrary graph topologies into a common representation and a GPU-optimized graph traversal engine. We conduct a comprehensive analysis across diverse datasets and state-of-the-art graph indices, introducing analysis metrics that quantify the relationship between structural properties and memory layout effectiveness. Our GPU-targeted reordering achieves up to 15$\%$ QPS improvements while preserving search accuracy, demonstrating that memory layout optimization operates orthogonally to existing algorithmic innovations. We will release all code upon publication to facilitate reproducibility and foster further research.
• Abstract（参考訳）: グラフに基づく近似近傍探索(ANNS)のGPU上でのグラフ並べ替え効果について,最初の系統的研究を行った。 グラフベースのANNSは、現代のAIアプリケーションにおいて支配的なパラダイムとなっているが、最近のアプローチでは、実行時間に大きな影響を与えるメモリレイアウトの考慮を無視しながら、アルゴリズムの革新に焦点を当てている。 我々の統合評価フレームワークは、任意のグラフトポロジを共通の表現に変換するグラフアダプタとGPU最適化グラフトラバーサルエンジンにより、異なるグラフインデックスにわたる多様な並べ替え戦略を包括的に評価することができる。 多様なデータセットと最先端グラフ指標を包括的に分析し、構造特性とメモリレイアウトの有効性の関係を定量化する分析指標を導入する。 検索精度を保ちながら最大15$\%のQPS改善を実現し、メモリレイアウトの最適化が既存のアルゴリズムの革新と直交的に動作することを示した。 我々は、再現性を促進し、さらなる研究を促進するために、出版時にすべてのコードを公開します。

関連論文リスト

• Global optimization of graph acquisition functions for neural architecture search [6.266977090949175]
  グラフベイズ最適化は、ニューラルネットワーク探索(NAS)のための強力でデータ効率のよいツールとしての可能性を示している。 本稿では,到達性や最短経路などの特性を含むグラフ入力空間の明示的な最適化式を提案する。 提案した符号化がグラフ空間の等価表現であることを理論的に証明し、ノードまたはエッジラベルを持つNAS領域に制限を与える。
  論文  参考訳（メタデータ） (2025-05-29T16:46:29Z)
• Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
  グラフ学習モデルは、協調フィルタリング(CF)ベースのレコメンデーションシステムに広くデプロイされている。 データ疎度の問題により、元の入力のグラフ構造は潜在的な肯定的な嗜好エッジを欠いている。 AGL-SC(Amplify Graph Learning framework)を提案する。
  論文  参考訳（メタデータ） (2024-06-27T08:26:20Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。 アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。 数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2024-05-26T08:17:13Z)
• Hierarchical Attention and Graph Neural Networks: Toward Drift-Free Pose Estimation [1.745925556687899]
  最もよく使われている3次元幾何登録法は、反復的なクローゼットポイントアルゴリズムである。 本稿では,階層型アテンション機構とグラフニューラルネットワークを用いた学習モデルを用いて,従来の幾何学的登録とポーズグラフ最適化を置き換えたフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-18T16:51:56Z)
• 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)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  埋め込みによるグラフリファインメントクラスタリングネットワーク (EGRC-Net) という新しいグラフクラスタリングネットワークを提案する。 EGRC-Netは学習した埋め込みを利用して初期グラフを適応的に洗練し、クラスタリング性能を向上させる。 提案手法はいくつかの最先端手法より一貫して優れている。
  論文  参考訳（メタデータ） (2022-11-19T09:08:43Z)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  グラフの外れ値検出は、多くのアプリケーションにおいて、新しいが重要な機械学習タスクである。 UNODと呼ばれるグラフに対して、最初の包括的教師なしノード外乱検出ベンチマークを示す。
  論文  参考訳（メタデータ） (2022-06-21T01:46:38Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
  グラフコントラスト学習(GCL)は、手作業によるアノテーションの監督なしに、グラフ表現学習(GRL)において有望な性能を示した。 本稿では,この課題に対処するため,グラフココというグラフ補完型コントラスト学習手法を提案する。
  論文  参考訳（メタデータ） (2022-03-24T02:58:36Z)
• Enhancing Balanced Graph Edge Partition with Effective Local Search [41.4257628524592]
  グラフパーティションは、ワークロードバランスを達成し、並列グラフ処理システムにおけるジョブ完了時間を短縮するための重要なコンポーネントです。 本稿では,本問題の局所探索アルゴリズムについて検討し,既存の手法による分割結果をさらに改善する。
  論文  参考訳（メタデータ） (2020-12-17T08:58:06Z)

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

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