論文の概要: Turbocharging PiPNN for Proximity and $k$-NN Graph Building

• arxiv url: http://arxiv.org/abs/2611.05690v1
• Date: Tue, 03 Nov 2026 22:20:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:57.889841
• Title: Turbocharging PiPNN for Proximity and $k$-NN Graph Building
• Title（参考訳）: 近接性と$k$-NNグラフ構築のためのターボチャージPiPNN
• Abstract要約: HNSWやVamanaといったグラフベースの近似Nearest Neighbor Search(ANNS)インデックスは、大量のインデックス処理を犠牲にして、最先端のクエリパフォーマンスを提供する。 最近導入されたPiPNN法は分割型アルゴリズムを用いて指数構築を大幅に高速化した。 グラフベースのANNSインデックス構築のための最大8倍のスピードアップを提供するPiPNN IIを導入し,PPNNレシピの複数のステップを最適化する。
• 参考スコア（独自算出の注目度）: 22.909618115970108
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph-based Approximate Nearest Neighbor Search (ANNS) indexes such as HNSW and Vamana deliver state-of-the-art query performance at the cost of large indexing times. The recently introduced PiPNN method drastically accelerated index construction by way of a partitioning-based algorithm leveraging dense matrix multiplication and top-$K$ aggregation kernels. In this paper, we unlock the full potential of PiPNN's hardware-friendly algorithm design. We introduce PiPNN II, which optimizes multiple steps of the PiPNN recipe, giving up to $8\times$ speedups for graph-based ANNS index construction. In addition, we present GPiPNN, a GPU implementation which builds comparable ANNS indices up to $43.7\times$ faster than Jasper and up to $50\times$ faster than CAGRA. We also extend PiPNN II and GPiPNN to compute high-quality $k$-NN graphs directly, which unlocks massive speedups over methods used in many existing systems for clustering, anomaly detection, and more. For 10-NN graph building at $90\%$ recall, we obtain up to a $13\times$ speedup on CPUs and $6.6\times$ on GPUs as compared to the prior best methods. PiPNN II can build a billion-scale 10-NN graph in under 16 minutes. Common to both PiPNN II and GPiPNN is the use of quantization to reduce memory traffic and leverage fast low-precision matrix operations. Top-$K$ emerges as a new bottleneck, which we optimize with specialized code for specific $K$, and by fusing with the matrix kernel to avoid materializing the distance matrix to memory. On CPUs, we demonstrate further performance improvements by leveraging our matrix kernels in the RobustPrune procedure proposed in Vamana and used in PiPNN. On GPUs, we flatten recursive partitioning into segmented batches, use one fused top-$K$ abstraction for partitioning and leaf scoring, and prune with already-witnessed direct edges rather than new candidate-to-candidate scoring passes.
• Abstract（参考訳）: HNSWやVamanaといったグラフベースの近似Nearest Neighbor Search(ANNS)インデックスは、大量のインデックス処理を犠牲にして、最先端のクエリパフォーマンスを提供する。 最近導入されたPiPNN法は、高密度行列乗算と上位$K$アグリゲーションカーネルを利用したパーティショニングに基づくアルゴリズムにより、指数構築を大幅に高速化した。 本稿では,PiPNNのハードウェアフレンドリなアルゴリズム設計の可能性について述べる。 グラフベースのANNSインデックス構築において,最大8\times$の高速化を付与し,PiPNNレシピの複数のステップを最適化するPiPNN IIを導入する。 さらに、同等のANNSインデックスを構築するGPU実装であるGPiPNNを、Jasperよりも最大43.7\times$、CAGRAより最大50\times$$で提供する。 PiPNN IIとGPiPNNも拡張して,高品質な$k$-NNグラフを直接計算します。 10-NNグラフを90-%のリコールで構築すると、CPUの13-times$スピードアップとGPUの6.6-times$を以前のベストメソッドと比較して得られる。 PiPNN IIでは,10億規模の10-NNグラフを16分以内で構築することができる。 PiPNN IIとGPiPNNの両方に共通しているのは、量子化を使ってメモリトラフィックを減らし、高速な低精度行列演算を利用することである。 Top-K$は、特定の$K$に対して特別なコードで最適化し、メモリへの距離行列の実体化を避けるためにマトリックスカーネルと融合することで、新しいボトルネックとして現れます。 CPU 上では,Vamana で提案され PiPNN で使用されている RobustPrune プロシージャで行列カーネルを活用することにより,さらなる性能向上を示す。 GPUでは、再帰的な分割をセグメント化されたバッチに平らにし、パーティショニングとリーフスコアリングのために1つの上位$K$の抽象化を使い、新しい候補から候補までのスコアリングパスではなく、すでに知名度の高い直接エッジでプルーンを使用する。

関連論文リスト

• GraphGP: Scalable Gaussian Processes with Vecchia's Approximation [0.0]
  ヴェッキア近似(Vecchia approximation)は、定常、崩壊する核に対するスパース精度行列近似である。 線形時間とメモリ要求で10億近いパラメータにスケールする,Vecchia近似のアルゴリズムであるGraphGPを提案する。
  論文  参考訳（メタデータ） (2026-06-09T19:50:27Z)
• PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing [6.243421401579046]
  PiPNNは、既存のグラフベースの手法が抱える「検索ボトルネック」を回避する、超スケーラブルグラフ構築アルゴリズムである。 HashPruneは、データセットを重複するサブプロブレムに分割し、バルク距離比較を効率的に実行し、エッジのサブセットをHashPruneにストリームすることを可能にする。 PiPNNはVamanaよりも最大11.6倍、HNSWより最大12.9倍高速な最先端インデックスを構築している。
  論文  参考訳（メタデータ） (2026-02-17T02:18:17Z)
• Graph Random Features for Scalable Gaussian Processes [52.89901965157282]
  離散入力空間上のスケーラブルなガウス過程へのグラフランダム特徴(GRF)の適用について検討する。 我々は、(穏やかな仮定の下で) GRF に対するベイズ的推論が、正確なカーネルに対して$O(N3)$のノード数に対して$O(N3/2)$の時間複雑性を楽しむことを証明した。
  論文  参考訳（メタデータ） (2025-09-03T20:13:23Z)
• MaxK-GNN: Extremely Fast GPU Kernel Design for Accelerating Graph Neural Networks Training [7.193336207798203]
  アルゴリズムとシステム革新を統合した高性能GPUトレーニングシステムMaxK-GNNを提案する。 実験により、マックスK-GNNシステムは、アムダールの法則に従って理論的なスピードアップ限界に接近できることが示された。 我々はSOTA GNNに匹敵する精度を達成したが、Redditでは3.22/4.24倍のスピードアップ(理論上の限界vs, 5.52/7.27倍)を実現した。
  論文  参考訳（メタデータ） (2023-12-14T05:00:49Z)
• SENSEi: Input-Sensitive Compilation for Accelerating GNNs [7.527596018706567]
  本稿では,GNN計算の行列再連想に基づいて,異なるスパースおよび密度行列プリミティブ構成を公開するシステムであるSENSEiを提案する。 SENSEiは、(1) 異なるスパースセンス行列合成につながるすべての有効な再連想を列挙するオフラインコンパイルステージで実行され、入出力プルーニング技術を用いて、明らかに利益のない候補を抽出する。 幅広い構成において、SENSEiは最大2.012times$と1.85times$のグラフ畳み込みネットワークで、最大6.294times$と16.274のスピードアップを達成する。
  論文  参考訳（メタデータ） (2023-06-27T02:24:05Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  我々は,超効率的なサイストリックアレイベースの多用途ハードウェアアクセラレータである textitVersaGNN を提案する。 textitVersaGNNは平均3712$times$ speedup with 1301.25$times$ energy reduction on CPU、35.4$times$ speedup with 17.66$times$ energy reduction on GPUを達成している。
  論文  参考訳（メタデータ） (2021-05-04T04:10:48Z)
• Hybrid Models for Learning to Branch [81.93868699246214]
  我々はCPUマシン上で効率的な分岐を行うための新しいハイブリッドアーキテクチャを提案する。 提案アーキテクチャは,GNNの表現力と分岐処理のための計算コストの低い多層パーセプトロン(MLP)を組み合わせる。
  論文  参考訳（メタデータ） (2020-06-26T21:03:45Z)

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

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