論文の概要: FROG: Efficient Range-Filtering Approximate Nearest Neighbor Search on GPUs
- arxiv url: http://arxiv.org/abs/2608.16491v1
- Date: Mon, 17 Aug 2026 12:29:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-18 19:59:03.68206
- Title: FROG: Efficient Range-Filtering Approximate Nearest Neighbor Search on GPUs
- Title（参考訳）: FROG:GPU上での効率的なレンジフィルタ近似近傍探索
- Authors: Xiaokun Cui, Pengbo Liu, Jiadong Xie, Yingfan Liu, Hui Li, Jeffrey Xu Yu, Jiangtao Cui,
- Abstract要約: 距離フィルタリング近似近傍探索(RFANNS)は、現代のベクトルデータベースにおける基本的な操作である。
我々は、複数の局所最適サブストラクチャ構築を置き換えるGPU指向RFANNSインデックスであるFROGを提案する。
FROGは14.7--37.7$times$44コアCPUベースライン以上、4.5--7.6$times$最強GPUベースライン以上である。
- 参考スコア（独自算出の注目度）: 19.82431161075971
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Range-filtering approximate nearest neighbor search (RFANNS) is a fundamental operation in modern vector databases. Given a query vector $q$ and a numerical range predicate, RFANNS returns the $k$-approximate nearest neighbors ($k$-ANN) of the query $q$ among the objects whose attributes satisfy the range predicate. However, existing RFANNS methods are not well suited to high-throughput GPU execution. CPU indexes offer limited parallel scalability, generic GPU filtering is highly selectivity-dependent, and GPU indexes built from locally optimized subgraphs can incur long search trajectories and redundant distance computations. To address these limitations, we present FROG, a GPU-oriented RFANNS index that replaces multiple locally optimal substructure building with a globally aware, vertex-centric design. It organizes diverse expansion neighbor candidates for each vertex in a GPU-friendly structure and rapidly identifies the expansion neighbors used for computation at query time. Moreover, GPU-oriented algorithms and implementations are developed for both index construction and query processing. Experiments on six datasets show that FROG improves mixed-selectivity query throughput by 14.7--37.7$\times$ over 44-core CPU baselines and 4.5--7.6$\times$ over the strongest GPU baseline. It also accelerates index construction by 2.4--14.8$\times$ over the GPU baseline.
- Abstract（参考訳）: 距離フィルタリング近似近傍探索(RFANNS)は、現代のベクトルデータベースにおける基本的な操作である。
クエリベクトル$q$と数値レンジ述語が与えられた場合、RFANNSは、範囲述語を満たす属性を満たすオブジェクトのうち、クエリの$q$の近辺($k$-ANN)を返します。
しかし、既存のRFANNS法は高スループットGPU実行には適していない。
CPUインデックスは、限られた並列スケーラビリティを提供し、汎用GPUフィルタリングは高い選択性に依存し、局所的に最適化されたサブグラフから構築されたGPUインデックスは、長い探索軌跡と冗長距離計算を発生させることができる。
これらの制約に対処するため、FROGはGPU指向のRFANNSインデックスで、複数の局所最適サブストラクチャをグローバルに認識し、頂点中心の設計で置き換える。
GPUフレンドリな構造で各頂点に対する多様な拡張隣候補を整理し、クエリ時に計算に使用される拡張隣候補を迅速に識別する。
さらに、インデックス構築とクエリ処理の両方のためにGPU指向のアルゴリズムと実装が開発されている。
6つのデータセットの実験は、FROGが混合選択クエリのスループットを14.7--37.7$\times$で44コアのCPUベースライン以上、4.5--7.6$\times$で改善していることを示している。また、GPUベースライン上でのインデックス構築を2.4-14.8$\times$で加速する。
関連論文リスト
- GraphGP: Scalable Gaussian Processes with Vecchia's Approximation [0.0]
ヴェッキア近似(Vecchia approximation)は、定常、崩壊する核に対するスパース精度行列近似である。
線形時間とメモリ要求で10億近いパラメータにスケールする,Vecchia近似のアルゴリズムであるGraphGPを提案する。
論文 参考訳（メタデータ） (2026-06-09T19:50:27Z) - GRAB-ANNS: High-Throughput Indexing and Hybrid Search via GPU-Native Bucketing [39.763467046232584]
動的ハイブリッド検索のためのGPUネイティブグラフインデックスであるGRAB-ANNSを提案する。
GRAB-ANNSは最新のCPUベースシステムよりも最大240.1倍高いクエリスループットと12.6倍高速なインデックス構築を実現する。
論文 参考訳（メタデータ） (2026-03-31T11:00:10Z) - GPU-Native Approximate Nearest Neighbor Search with IVF-RaBitQ: Fast Index Build and Search [6.459073253087106]
IVF-RaBitQは、クラスタベースのIVFとRaBitQ量子化を統合したGPUネイティブなANNSソリューションで、効率的なGPUインデックスの構築/検索パイプラインである。
IVF-RaBitQは、リコール、スループット、インデックスビルド時間、ストレージフットプリントにおいて、強力なパフォーマンスフロンティアを提供する。
論文 参考訳（メタデータ） (2026-02-27T13:23:30Z) - GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
本稿では,GPU加速グラフに基づくベクトル探索アルゴリズムについて包括的に研究する。
我々は、GPU最適化戦略の詳細な分類を確立し、アルゴリズムタスクとハードウェア実行ユニット間のマッピングを明確にする。
我々の発見は、スケーラブルで堅牢なGPUベースの近接検索システムを設計するための明確なガイドラインを提供する。
論文 参考訳（メタデータ） (2026-02-10T16:18:04Z) - NGPU-LM: GPU-Accelerated N-Gram Language Model for Context-Biasing in Greedy ASR Decoding [54.88765757043535]
この研究は、統計的なn-gram言語モデルのデータ構造を再考し、GPU最適化推論の高速かつ並列な操作を可能にする。
我々のアプローチは NGPU-LM と呼ばれ、7% 未満の計算オーバーヘッドを持つ全ての主要な ASR モデルに対して、カスタマイズ可能なgreedy decoding を導入している。
提案手法は,ビーム探索による顕著な遅延を回避しつつ,greedy と beam search の精度ギャップの50%以上を排除できる。
論文 参考訳（メタデータ） (2025-05-28T20:43:10Z) - iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search [24.85572470526277]
周辺地域を探索するRFANN(Range-filtering Near Near Near Near neighbor)は、学術や産業で注目を集めている。
最近の研究では、可能な全てのクエリ範囲に対して、$O(n2)$専用のグラフベースのインデックスを構築することを提案する。
要素グラフと呼ばれるグラフベースのインデックスを適度な範囲で作成する。
論文 参考訳（メタデータ） (2024-09-04T09:41:52Z) - 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) - 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 Improving the Consistency, Efficiency, and Flexibility of
Differentiable Neural Architecture Search [84.4140192638394]
最も微分可能なニューラルアーキテクチャ探索法は、探索用のスーパーネットを構築し、そのサブグラフとしてターゲットネットを導出する。
本稿では,エンジンセルとトランジットセルからなるEnTranNASを紹介する。
また,検索処理の高速化を図るため,メモリや計算コストの削減も図っている。
論文 参考訳（メタデータ） (2021-01-27T12:16:47Z) - Hybrid Models for Learning to Branch [81.93868699246214]
我々はCPUマシン上で効率的な分岐を行うための新しいハイブリッドアーキテクチャを提案する。
提案アーキテクチャは,GNNの表現力と分岐処理のための計算コストの低い多層パーセプトロン(MLP)を組み合わせる。
論文 参考訳（メタデータ） (2020-06-26T21:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。