WWW2025 | 小红书向量检索团队提出超大规模向量检索图索引构建新方法
等你加入的约 9 分钟在 WWW2025 会议上，小红书提出了面向百亿级向量数据库的可扩展过载感知图索引构建系统 SOGAIC。该系统通过自适应重叠划分算法缓解数据不均带来的资源过载问题，并结合负载均衡的任务调度与聚合式分层子图合并策略，实现高效并行构建。实验显示，SOGAIC 在多个真实数据集上平均减少 47.3% 的构建时间，具备良好的扩展性，已部署于小红书在线向量检索引擎，支撑百亿级向量的日更新需求。
论文标题：
Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search
论文地址：
https://arxiv.org/abs/2502.20695
1.1 概述
近似最近邻搜索（ANNS）因其在搜索引擎、推荐系统以及大语言模型中的检索增强生成（RAG）等关键任务中的广泛应用，近年来受到广泛关注。在众多 ANNS 算法中，图结构方法（如 HNSW、NSG 和 NGT）凭借其优秀的邻居关系表达能力和高搜索精度，已成为主流选择，尤其在对比传统的空间划分方法（如 IVF、KD-Tree 和 LSH）时更具优势。随着向量数据库规模扩展至数百亿级，面向大规模检索场景的图索引构建方法如 DiskANN 等被提出，用以降低内存使用与磁盘 I/O 压力。然而，这类依赖分而治之策略的构建方法通常难以高效扩展，限制了其在实际应用中对索引的高频更新与快速构建需求的支持。
1.2 挑战
重叠划分中的冗余与过载问题
现有方法在大规模数据集上实现高效且具备过载感知的数据划分仍面临挑战。以 DiskANN 为例，其通过将每个向量分配到距离最近的若干聚类中心所对应的子集来引入重叠，但这种固定重叠策略往往会导致几何上相邻子集之间出现冗余重叠，同时由于 K-means 聚类样本数量有限，还容易造成向量分布不均，导致部分子集出现资源过载问题，严重影响后续子图构建的稳定性与效率。尽管基于密度的划分方法如 DBSCAN 能提供更精细的划分，但其高计算成本、参数敏感性以及无法控制中心数量等问题使其难以应用于超大规模场景。因此，亟需一种更具适应性的数据划分策略，以在控制过载的同时减少不必要的重叠。
构图与合并阶段的调度扩展性不足
现有图索引构建方法在子图构建与合并阶段普遍缺乏高效且可扩展的调度框架。以 DiskANN 为代表的主流方法通常依赖单台高性能机器顺序构建并合并子图，这种串行流程严重限制了整体的构建效率与系统可扩展性。尽管如 SPTAG 等系统引入了面向非重叠划分的数据分发机制，将任务分配至集群中执行，具备一定的扩展能力，但在数据规模进一步扩大后，为确保图结构连通性所需的重叠优化过程需反复迭代，导致计算与存储开销显著增加。考虑到子图构建时间与子集大小近似线性相关，若能在划分阶段控制重叠范围与负载上限的同时，结合任务优先级与资源使用策略，便有望构建出高效、负载均衡的分布式调度框架，以显著缩短整体构建流程。
1.3 动因
为克服上述的不足，我们提出了 SOGAIC，首个可扩展的超载感知 ANNS 图索引构建系统。SOGAIC 通过自适应数据分区策略和负载均衡任务调度框架加速索引构建，确保系统能够在计算资源允许的范围内扩展，同时保持高质量的图结构，从而实现高效的向量相似度搜索。
2.1 系统概述
该系统主要由两个阶段组成。第一阶段通过自适应数据分区算法处理重叠子集的划分，同时控制过载边界。第二阶段在分布式集群上调度子图构建任务，并执行层次化合并策略以形成最终的 ANNS 图索引。
2.2过载感知的自适应数据分区算法
该算法首先基于计算集群中容器的内存限制确定每个分区的最大容量 Γ（即基准点数上限），并结合数据集总规模N及最大重叠因子 Ω（表示单个点可归属的分区数上限），动态估算处理高度不平衡数据分布所需的最小分区数 Φ。通过在小规模数据样本上执行 K-means 聚类，生成 Φ 个初始中心点作为分区划分的几何参考。在此基础上，提出一种基于动态距离约束的向量分配方法：对于每个点，其到中心点的距离需小于当前已分配点的平均距离，并通过自适应松弛参数 ε 进行缩放调整。其中，ε 的取值随数据分布特性灵活变化——对均匀分布数据采用较小的 ε 以减少冗余分配，而对结构复杂的数据则采用较大的 ε 以增强分区间重叠，从而提升后续图结构的连通性。当某一分区达到容量 Γ 的过载阈值时，系统自动重置平均距离参数，确保所有点至少被分配至一个有效分区。此外，由于向量分配任务具备独立性和低内存占用的特点，系统将量化编码与分配过程并行化执行，完全避免了冗余计算，相较于 DiskANN 等顺序处理方法显著提升了效率。
2.3分布式图构建与层次化子图合并策略
本节提出一种专为分布式计算环境设计的高效子图构建与合并策略。首先，基于 ANNS 图构建时间与数据集规模的近似线性关系，采用负载均衡调度方法优化任务分配：将前一阶段生成的子集按大小降序排序，优先处理规模较大的任务以平衡集群负载；随后，通过迭代选择当前负载最小的机器或容器动态分配任务，确保每项任务对整体负载的增量贡献最小化，从而最大化资源利用率。在子图合并阶段，采用层次化策略提升效率：利用 Apache Spark 或 MapReduce 等分布式框架，将已完成的子图异步交换至不同节点进行多级合并。其中，计算密集型操作聚焦于重叠区域的邻居选择与优化，非重叠部分则直接继承至下一阶段，避免冗余计算。通过树状分层结构，合并复杂度从传统方法的 O(n) 降低至 O(log n)。与 DiskANN 依赖磁盘合并的策略不同，本框架优先对可驻留于内存的子图执行内存级合并，既减少 I/O 瓶颈，又通过即时访问向量距离实现更精准的邻居筛选，从而提升最终图结构的检索质量。此外，通过实时监控子图间的重叠比例，动态调整合并优先级——重叠度高的子图优先合并，进一步加速整体流程并优化资源分配。
3.1 实验设置
数据集
实验在五个数据集上进行，包括图像向量（SIFT1M、SIFT1B 和小红书图搜数据集 ISD3B）、文本向量（GloVe）以及视频向量（小红书安审重复视频数据集 VDD10B）。表1总结了这些数据集的主要特性，其中 LID 表示局部内在维度，用于衡量数据集的检索难度。
对比方法
选取以下方法与本文提出的 SOGAIC 进行对比：
HNSW：基于 Faiss 库的 ANNS 图索引实现。
DiskANN：面向磁盘优化的 ANNS 图索引方法。
SPTAG：支持分布式计算的 ANNS 图索引库。
评估指标
性能：在固定 CPU 核心数下，测量索引构建时间与召回率的权衡。
可扩展性：在保持召回率恒定的条件下，追踪构建时间随 CPU 核心数增加的变化趋势。
控制变量：为确保公平性，所有方法均使用相同的图结构配置，并取多次实验的平均值以减少偏差。
3.2 实验结果与分析
构建性能
如图（左列）所示，在超过 SIFT1M 规模的所有数据集上，SOGAIC 相比基线方法平均减少了 47.3% 的构建时间。对于十亿级数据集（如 SIFT1B），Faiss 的 HNSW 实现因内存不足而失败；在 LID 较高的 ISD3B 数据集上，DiskANN 因数据分区严重失衡而无法完成构建，而 SPTAG 需多次迭代引入重叠区域，导致耗时显著增加。相比之下，SOGAIC 通过动态调整重叠因子（预设最大值 Ω=4，实际平均每个向量仅分配至 1.93 个子集），在避免过载的同时减少了冗余计算，最终实现了更高的效率与可扩展性。
系统可扩展性
如图（右列）所示，SOGAIC 的构建时间随计算资源增加呈近线性下降趋势。例如，在处理超大规模高维数据集 VDD10B 时，SPTAG 在 128 CPU 下耗时超过 100 小时（目标召回率 0.95），而 DiskANN 因扩展性不足导致耗时居高不下。SOGAIC 在同等配置下仅需约 80 小时，且在使用 512 CPU 时可进一步缩短至 1 天以内。这一优势得益于负载均衡调度框架与层次化合并策略的结合，使得系统能够高效利用分布式资源。
本文提出了可扩展的过载感知图索引构建系统 SOGAIC，针对百亿级向量数据库的构建挑战，设计自适应重叠划分算法缓解数据分布不均导致的资源过载，结合负载均衡调度与分层子图合并策略实现高效并行化。实验显示，SOGAIC 在真实场景中平均降低 47.3% 的构建时间，具备强扩展性，并已落地小红书搜索推荐审核等在线引擎，支持百亿级向量日更新及毫秒级检索服务。
该论文部分技术已于今年2月申请专利保护并于今年5月公开：
海民（石旸）
负责小红书向量数据库研发，在向量检索算法以及搜推广引擎等领域有丰富的落地实践经验。
安多（孙一平）
负责小红书向量数据库研发，在信息检索、搜推广引擎以及RAG等领域有丰富的落地实践经验。
明诚（钟晓诚）
负责小红书索引存储架构团队，在搜推广方向的数据分布式存储和高性能混合检索等领域有丰富的落地实践经验。
引擎架构开发
【工作职责】
1、深度参与小红书搜索/推荐/广告业务，满足产品、算法对于核心引擎或者基础平台的功能需求，抽象通用的业务开发框架与组件，提升业务支持效率，将现有技术逐步平台化和产品化；
2、负责攻克服务中高并发、高可靠性、高扩展性、高稳定性、业务复杂等带来的各种挑战及技术难关，能够基于领域架构以及微服务定义业务模型和服务等，识别当前架构中存在的问题，并推动架构升级，体系化地解决问题；
3、参与搜索引擎、推荐引擎、模型预测、向量检索等大规模算法服务系统、平台的设计、研发及调优工作，提升效率降低成本，对xtr、bert、LLM、搜推、cvnlp等模型进行深度优化，通过算子融合、模型压缩、量化等手段优化现有模型推理性能，设计并实现高效的分布式离线推理方案，支持高效的离线批量模型推理，并支持业务的大模型相关探索，如LLM的AI能力在问答、客服等多个场景的落地；
4、负责深度学习领域的调研和技术引入，通过新硬件、新技术的落地，持续提升模型能力。
【任职资格】
1、本科及以上学历；计算机等相关专业优先；
2、编程基本功扎实，具有扎实的数据结构和算法功底，熟悉常用的设计模式、软件架构模式、计算网络、操作系统，擅长Java/C++至少一门语言；
3、熟悉微服务、消息队列、MYSQL、缓存等技术，深入了解Transformer、LLM 模型者，熟悉 tensorflow/pytorch等训练推理框架，掌握GPU等的高性能计算优化技巧优先；
4、 在Github上拥有有影响力的开源项目，或者是行业著名开源项目的核心贡献者优先，参加过ACM竞赛者优先，对推荐前沿技术有了解的优先；
5、优秀的分析、抽象、解决问题能力，对新技术充满好奇，敢于挑战高难度，善于提出解决方案并快速验证。
欢迎感兴趣的同学发送简历至 [email protected]
并抄送至下方邮箱以获得最快速响应：
添加小助手，了解更多内容
微信号 / REDtech01