✨ 要点🔬 技术摘要
想象一下，你正站在一座巨大的、隐形的图书馆里，里面藏着数十亿本书。但这些书的脊背上没有书名，而是由一段描述其内容的秘密且复杂的代码来定义的。你产生了一个新想法，仅仅是一个句子，而你想在整座图书馆中找到与它最相似的五本书。这就是**近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）**的世界。在数字时代，这不仅仅关乎书籍；它是为你推荐下一首最爱歌曲、在数百万人中寻找相似面孔，或帮助人工智能理解你所问内容的引擎。问题在于，图书馆如此庞大，代码如此复杂，如果逐一检查每一本书，将耗费无穷的时间。因此，科学家们建造了“捷径”——特殊的地图，让你能够快速缩放到正确的区域，而无需阅读整个目录。
然而，为编写这些软件的人来说，构建这些捷径一直是个令人头疼的问题。多年来，他们面临着一个令人沮丧的选择：是构建一个速度极快、高性能但僵化且难以更改的捷径，还是构建一个灵活、功能丰富但速度稍慢的系统。这就像是在选择一辆只能在赛道上行驶的 F1 赛车，或者一辆虽然缓慢但可以去任何地方的越野卡车。想要同时拥有高速和适应性的开发者，曾不得不花费数年时间拼凑代码，结果往往得到的是要么太慢，要么太笨重的产物。
于是，由研究员沈哲奇、苏静波及其团队提出的新工具包 ANNLib 登场了。请不要把 ANNLib 仅仅看作一辆车，而要把它看作一套用于构建这些搜索捷径的高科技“乐高组件”。研究人员意识到，搜索系统的两个主要部分——算法 （搜索逻辑）和数据结构 （地图物理存储的方式）——通常被紧紧地粘在一起。ANNLib 精心将它们剥离开来。它提供了一个由预制、超优化“乐高积木”组成的库，涵盖了逻辑和存储两个方面。你可以将“Vamana”逻辑积木与“功能树”存储积木拼接在一起，或者加入一个“过滤器”模块，以便只搜索封面为红色的书。
论文表明，通过使用这种模块化方法，开发者可以用极少的代码构建出复杂的、专门化的搜索系统。但令人兴奋的部分在于：该团队不仅让构建变得更容易，还让它变得更快。他们在包含高达 1 亿个点的海量数据集上进行的实验表明，使用 ANNLib 构建的系统与作为行业标准的那些专门化、“难以更改”的系统一样快，甚至往往更快。无论他们是需要处理频繁更新（例如每天添加新书）、按特定标签过滤结果，还是甚至查看图书馆在过去的某个时间点的“快照”，ANNLib 都能轻松应对。作者们直接测量了这种性能，发现他们的灵活框架可以匹配甚至超越专门化工具的速度，证明了你不需要为了获得灵活性而牺牲速度。简而言之，ANNLib 表明，未来寻找“大海捞针”并不需要为每项工作都制造一台新机器；它只需要一套更好的工具，让你能快速造出合适的机器。
技术摘要：ANNLib —— 一种用于高效近似最近邻搜索的开发框架
1. 问题陈述
近似最近邻搜索（ANNS）是现代深度学习流水线中的关键组件，它实现了高维向量空间中的高效检索。尽管已有大量研究致力于扩展 ANNS 系统的功能性（例如支持动态更新、过滤或历史快照）或最大化性能（吞吐量和召回率），但很少有系统能以极低的编程工作量同时实现这两者。
目前的解决方案面临着一种二分困境：
功能丰富的向量数据库 （如 Milvus、Weaviate）优先考虑易用性，但在性能上往往逊于专门的算法。性能优化的系统 （如 DiskANN、ParlayANN）提供高吞吐量，但由高度优化的单体代码库组成，难以适配新的功能或特定应用的约束。
开发者被迫在性能与灵活性之间做出选择，通常需要进行大量的代码重写，才能在现有的高性能引擎之上实现过滤搜索或动态删除等高级功能。
2. 方法论：ANNLib 框架
作者提出了 ANNLib ，这是一个 C++ 头文件库，旨在将基于图的 ANNS 系统的算法逻辑与数据结构组件解耦。该框架允许开发者通过组合预构建的、深度优化的模块来构建高性能的 ANNS 系统。
2.1 核心设计原则
解耦与模块化： ANNLib 将系统分为两个独立的内核组件：算法（Algorithms）与 数据结构（Data Structures） 。
算法： 提供索引构建和查询的逻辑。ANNLib 包含了基础算法（Vamana、HNSW、HCNNG）以及用于高级功能的算法模块（批量插入、删除、过滤搜索、快照）。数据结构： 管理底层的图表示。ANNLib 提供了统一的接口来读取和修改图，支持多种容器类型（例如用于静态工作负载的嵌套数组 Nested Arrays、用于快照的函数树 Functional Trees，以及一种新型的 Chrono Prefix Array）。
通用逻辑抽象： 框架将通用的图操作（特别是邻居收集和剪枝）抽象为通用接口（collect 和 prune）。开发者只需实现其特定算法的独特逻辑，即可复用共享的并行化和遍历逻辑。边缘代理模式（Edge Agent Pattern）： 为了在不向算法开发者暴露容器特定细节的情况下支持多样化的数据结构，ANNLib 引入了“边缘代理”。这种中间结构作为顶点边的一个视图，允许容器应用自身的优化（例如，对树使用写时复制 Copy-on-Write，对嵌套数组进行直接数组访问），同时呈现统一的接口给算法。
2.2 关键技术实现
过滤搜索（Filtered Search）： 通过 Stitched-vamana（合并按标签构建的子图）和 Filtered-vamana（放宽剪枝条件以保留具有特定标签的候选对象）来实现。这两者都是通过定制邻居过滤谓词（f_nbhs）而无需改变核心束搜索（beam search）逻辑来实现的。动态更新（删除）： 基于 FreshDiskANN 方法，ANNLib 实现了一个两阶段过程：标记已删除的点（使用状态数组和用于快速路径检查的“墓碑”逻辑）并合并邻居以恢复图的连通性。历史快照（Historical Snapshots）： 框架支持查询索引的历史状态。它引入了两种数据结构：
函数树 (CPAM)： 使用写时复制（CoW）来保留版本。Chrono Prefix Array： 一种专门针对 ANNS 图设计的新型结构，通过共享前缀来压缩随时间变化的边版本。这避免了在快照中重复复制边，与全量树拷贝相比，显著降低了内存开销。
2.3 应用示例
论文通过在 ANNLib 之上以极少的代码构建四个应用，展示了该框架的灵活性：
常规 ANNS： 使用 Vamana 或 HNSW 的标准静态搜索。全动态更新： 支持批量插入和删除。过滤搜索： 实现 Stitched-vamana 和 Filtered-vamana。带快照的流式处理： 维护索引的历史版本以进行时间序列查询。
3. 实验结果
作者在多个数据集（BIGANN、DEEP、OpenAI、Cohere、MARCO、YFCC）和场景下，将 ANNLib 与最先进的基准测试（ParlayANN、DiskANN、Milvus、Weaviate）进行了对比评估。
插入性能： ANNLib 的 Vamana 实现比 ParlayANN 平均提升了 1.58× ，在特定批次中甚至达到了 8.11× 的加速。HNSW 的性能与 ParlayHNSW 相当（0.99–1.34× 加速）。这些增益归功于消除拷贝（copy elision）和优化的接口。查询吞吐量（常规搜索）： ANNLib 实现了具有竞争力的 QPS-召回率权衡。在 BIGANN 等大型数据集上，其性能与 ParlayANN 持平。在较小的数据集上，它在高召回率时收敛到相当的 QPS，尽管它缺乏 ParlayANN 中存在的专门针对低召回率的优化。过滤搜索： 在几乎所有关于 QPS-召回率曲线的案例中，ANNLib 的表现都优于单体解决方案（DiskANN、Milvus、Weaviate），证明了模块化设计并不会牺牲性能。删除： ANNLib 中的合并阶段使索引召回率恢复到了接近重建的水平，尽管这会产生与受影响点数成正比的计算成本。快照： 与朴素的按时间顺序列表方案相比，Chrono Prefix Array 通过避免完整的边复制，将内存使用量降低了高达 70.4% 。虽然启用快照增加了构建时间（根据结构不同，为 1.22× 到 3.32×），但其内存效率的提升对于大规模动态数据集而言意义重大。
4. 核心贡献
一个模块化框架： ANNLib 提供了第一个成功将算法逻辑与数据结构实现解耦的基于图的 ANNS 编程框架，实现了灵活的组合。统一的抽象： 引入通用 collect/prune 接口和 Edge Agent 模式，使得多样化的算法和数据结构能够无缝互操作。新型数据结构： 提出的 Chrono Prefix Array 为维护动态图的历史快照提供了一种空间高效的解决方案，解决了现有快照机制中的特定瓶颈。验证了灵活性与性能： 论文证明了可以利用极少的代码实现复杂功能（过滤、删除、快照），同时达到与专门的单体系统相当甚至更优的性能。
5. 重要性与主张
论文声称 ANNLib 弥合了高性能研究原型与灵活的生产就绪系统之间的鸿沟。通过允许开发者“即插即用”优化组件，ANNLib 在不牺牲效率的前提下，降低了构建复杂 ANNS 系统所需的工程量。
作者强调，其设计使得创建混合系统（例如，在动态变化的数据集的历史快照上执行过滤查询）成为可能，而这在现有的单体框架中是难以实现的。代码的发布旨在促进 ANNS 领域的进一步研究与应用开发。
每周获取最佳 machine learning 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。