論文の概要: PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing
- arxiv url: http://arxiv.org/abs/2602.21247v1
- Date: Tue, 17 Feb 2026 02:18:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-26 18:19:16.545403
- Title: PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing
- Title（参考訳）: PiPNN:超スケーラブルなグラフベースの周辺インデックス
- Authors: Tobias Rubel, Richard Wen, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram, Jakub Łącki,
- Abstract要約: PiPNNは、既存のグラフベースの手法が抱える「検索ボトルネック」を回避する、超スケーラブルグラフ構築アルゴリズムである。
HashPruneは、データセットを重複するサブプロブレムに分割し、バルク距離比較を効率的に実行し、エッジのサブセットをHashPruneにストリームすることを可能にする。
PiPNNはVamanaよりも最大11.6倍、HNSWより最大12.9倍高速な最先端インデックスを構築している。
- 参考スコア（独自算出の注目度）: 6.243421401579046
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The fastest indexes for Approximate Nearest Neighbor Search today are also the slowest to build: graph-based methods like HNSW and Vamana achieve state-of-the-art query performance but have large construction times due to relying on random-access-heavy beam searches. We introduce PiPNN (Pick-in-Partitions Nearest Neighbors), an ultra-scalable graph construction algorithm that avoids this ``search bottleneck'' that existing graph-based methods suffer from. PiPNN's core innovation is HashPrune, a novel online pruning algorithm which dynamically maintains sparse collections of edges. HashPrune enables PiPNN to partition the dataset into overlapping sub-problems, efficiently perform bulk distance comparisons via dense matrix multiplication kernels, and stream a subset of the edges into HashPrune. HashPrune guarantees bounded memory during index construction which permits PiPNN to build higher quality indices without the use of extra intermediate memory. PiPNN builds state-of-the-art indexes up to 11.6x faster than Vamana (DiskANN) and up to 12.9x faster than HNSW. PiPNN is significantly more scalable than recent algorithms for fast graph construction. PiPNN builds indexes at least 19.1x faster than MIRAGE and 17.3x than FastKCNA while producing indexes that achieve higher query throughput. PiPNN enables us to build, for the first time, high-quality ANN indexes on billion-scale datasets in under 20 minutes using a single multicore machine.
- Abstract（参考訳）: HNSWやVamanaのようなグラフベースの手法は、最先端のクエリのパフォーマンスを達成しているが、ランダムアクセスの重いビームサーチに依存するため、建設時間は長い。
我々は,既存のグラフベースの手法が抱える「検索ボトルネック」を回避する,超スケーリング可能なグラフ構築アルゴリズムであるPiPNN(Pick-in-Partitions Nearest Neighbors)を紹介する。
PiPNNの中核となる革新はHashPruneである。
HashPruneは、データセットを重複するサブプロブレムに分割し、密度の高い行列乗算カーネルを介してバルク距離比較を効率よく実行し、エッジのサブセットをHashPruneにストリームすることを可能にする。
HashPruneはインデックス構築中にバウンドメモリを保証するため、PiPNNは追加の中間メモリを使わずに高品質なインデックスを構築することができる。
PiPNNはVamana(DiskANN)よりも最大11.6倍、HNSWより最大12.9倍高速な最先端インデックスを構築している。
PiPNNは、高速グラフ構築のための最近のアルゴリズムよりもはるかにスケーラブルである。
PiPNNは、MIRAGEより少なくとも19.1倍、FastKCNAより17.3倍高速なインデックスを作成し、高いクエリスループットを実現するインデックスを生成する。
PiPNNは、初めて、単一のマルチコアマシンを使用して、数十億規模のデータセット上の高品質なANNインデックスを20分以内で構築できます。
関連論文リスト
- Multiple Index Merge for Approximate Nearest Neighbor Search [14.386466486046814]
本稿では、AKNN検索のための効率的な2次元統合と複数のインデックスのマージ順序について述べる。
本稿では,構造情報を活用してマージ効率を向上させるリバース隣り合うスライディング・マージ(RNSM)を提案する。
実験の結果,既存のインデックスマージ法よりも5.48$times$スピードアップ,9.92$times$インデックス再構成よりも9.92$times$スピードアップが得られた。
論文 参考訳（メタデータ） (2026-02-19T05:50:34Z) - B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index [3.4720326275852]
本稿では,HNSWアルゴリズムの問題点に対処するため,新しいディスクベースANNインデックスであるB+ANNを提案する。
入力データをセマンティックに類似したアイテムを含むブロックに分割し、B+ツリーの変種を構築し、インメモリとディスクの両方にブロックを格納する。
HNSWよりも品質(リコール値)と実行性能(秒/QPSあたりのクエリ)の両方を改善する。
論文 参考訳（メタデータ） (2025-11-19T15:50:28Z) - CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search [9.557937699715124]
近似近接探索(ANNS)は、情報検索とAIアプリケーションにおいて重要な問題である。
本稿では,不必要な距離計算をバイパスするCRoutingという新しいルーティング手法を提案する。
実験により、CRoutingは、最大41.5%までの距離計算を削減し、2つの主要なグラフインデックス上で、毎秒1.48$times$までクエリを高速化することを示した。
論文 参考訳（メタデータ） (2025-08-30T05:27:09Z) - In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search [12.092920351505036]
IP-DiskANNは,挿入処理と削除処理を効率よく行うことにより,バッチ統合を回避する最初のアルゴリズムである。
ハイリコールとローリコールの両方で、様々な長い更新パターンに対して安定したリコールを行う。
論文 参考訳（メタデータ） (2025-02-19T15:41:08Z) - Compact Neural Graphics Primitives with Learned Hash Probing [100.07267906666293]
学習したプローブを持つハッシュテーブルにはデメリットはなく,その結果,サイズと速度の組合せが好適であることを示す。
推論は、トレーニングが1.2-2.6倍遅い間、同じ品質で未処理のハッシュテーブルよりも高速である。
論文 参考訳（メタデータ） (2023-12-28T18:58:45Z) - 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) - Accelerating Barnes-Hut t-SNE Algorithm by Efficient Parallelization on
Multi-Core CPUs [59.18990342943095]
t-SNEは高次元データを視覚化するための最も一般的な埋め込み技術の一つである。
BH t-SNEアルゴリズムは既存のCPU実装では非効率である。
Acc-t-SNEはScikit-learnよりも最大261倍、4倍高速で、daal4pyの最先端のBH t-SNE実装である。
論文 参考訳（メタデータ） (2022-12-22T06:38:40Z) - 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) - FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor
Search [20.928821121591493]
効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。
FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。
実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
論文 参考訳（メタデータ） (2022-06-22T22:30:46Z) - Scalable Graph Neural Networks via Bidirectional Propagation [89.70835710988395]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータを学習するための新興分野である。
本稿では、特徴ベクトルとトレーニング/テストノードの両方から局所的な双方向伝搬プロセスを利用するスケーラブルなGNNであるGBPを提案する。
実証実験により、GBPは、トレーニング/テスト時間を大幅に減らして最先端のパフォーマンスを達成することが示された。
論文 参考訳（メタデータ） (2020-10-29T08:55:33Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。