arXiv:2608.16491cs.DBcs.IR2026-08

FROG提升向量数据库范围过滤近邻搜索效率,适合高吞吐GPU场景。

FROG: Efficient Range-Filtering Approximate Nearest Neighbor Search on GPUs

论文配图:FROG: Efficient Range-Filtering Approximate Nearest Neighbor Search on GPUs
图 1 · 摘自论文原文
  • 采用全局感知的顶点中心设计,优化GPU上邻居扩展结构组织。
  • 在6个数据集上查询吞吐量比44核CPU快14.7至37.7倍。
  • 适用于需要高速范围过滤近邻搜索的向量数据库系统。

范围过滤近邻搜索(RFANNS)是现代向量数据库的核心操作。给定查询向量 $q$ 和数值范围谓词,RFANNS 返回满足范围条件的对象中 $k$-近似最近邻($k$-ANN)。然而,现有方法难以高效适配高吞吐GPU执行:CPU索引并行扩展有限,通用GPU过滤高度依赖选择性,基于局部优化子图构建的GPU索引存在长搜索路径和冗余距离计算。为此,本文提出FROG,一种面向GPU的RFANNS索引,以全局感知的顶点中心设计替代多个局部最优子结构构建。它为每个顶点组织多样化的扩展邻居候选,在查询时快速识别实际参与计算的邻居。同时开发了针对索引构建与查询处理的GPU优化算法与实现。在六个数据集上的实验表明,FROG相比44核CPU基线提升混合选择性查询吞吐量14.7–37.7×,相比最强的GPU基线提升4.5–7.6×;索引构建速度也比GPU基线快2.4–14.8×。

原文摘要 · Abstract (English)

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.

向量数据库近邻搜索GPU优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。