问题背景#

图索引合并后具有查询优势在一个大图上做k-ANNS的开销几乎总是好于在若干小图上做k-ANNS, 比如在单个HNSW图索引上的k-ANNS通常是 $O(log n)$ 级别的开销, 由于 $O(\Sigma \log n) > O(\log \Sigma n)$ , 因此合并小图可以很好地提升k-ANNS的性能.
RAG等工业应用需要图索引支持连续数据写入, 虽然HNSW天然支持增量插入能力, 但维护整个图索引需要非常大的空间, 无法在内存中处理. 一种方法是用内存维护一个较小的图索引, 然后周期性地写入硬盘, 但由于需要周期性地进行重建以保证搜索质量, 这种方式的计算代价过于昂贵.
分布式系统和并行计算善于处理多个小图索引的构建, 同时可能具有集群合并的需求, 这同时需要合并各个计算节点的数据索引.

问题定义#

向量图索引: 从 $d$ 维向量空间 $\mathbb{R}^d$ 中点集 $D$ 到简单有向图的映射 $f_{ind}: D\rightarrow (V, E)$ . 建立向量图索引的代价为 $cost(D)$

向量图索引的合并: 假设现在有 $n$ 个 $d$ 维向量图索引 $f_{ind}(D_1), f_{ind}(D_2), \cdots, f_{ind}(D_n)$ , 目标是构造搜索性能好的图索引. 构造代价为 $cost_{merge}(D_1, D_2, \cdots, D_n)$

目标函数:

最大化 $cost(D_1 \cup D_2 \cup \cdots \cup D_n) - cost_{merge}(D_1, D_2, \cdots, D_n)$ .
最大化合并图索引的搜索质量, 通过 $\operatorname{Recall@}k-QPS$ 曲线评价.

baseline#

简单合并边: 也就是认为 $\hat{f}_{ind}(\cup D_i) = \cup f_{ind}(D_i)$ , 这通常具有最好的cost, 但是全图的图索引不连通, 通常搜索效果 $\operatorname{Recall@}K$ 较差.
分别搜索: 不做合并, 每次查询都每个图索引上进行一次kNNS, 最终取所有kNNS的并集的前k项. 这样的cost项最好, 但是 $QPS$ 会随着索引数量的增加显著下降.
全局重建, 这样的 $cost$ 项最差, 但是 $Recall@K$ 和 $QPS$ 比较好.
增量构建, 即将 $D_2, D_3, \cdots, D_n$ 中的点逐点插入 $D_1$ 中. 适用于HNSW等支持增量构建的图索引, 但如NSG和Vamana等图索引通常不支持增量构建.

challenge#

全局重建和增量构建的问题在于: 没有利用已有的图索引 $f_{ind}(D_i)$ 中的信息, 直观上, 建立已有图索引的过程已经包含了大量距离计算和比较, 直接忽略已有图索引相当于没有复用这些已有的计算结果, 会产生很多重复计算.

而简单合并边充分利用了(完全使用)已有图索引的边, 但问题在于: 合并后的图索引的边会发生改变, 添加一些新边, 删除一些旧边, 而简单合并边没有进行合并后的修正, 导致合并后的图索引质量较差.

我们认为目前的challenges有以下这些:

复用已有结构问题. 已有图索引中已经含有近邻边和导航边, 合并算法需要判断哪些已有结构在全局图中仍然有效.
建立跨图结构问题. 需要通过较低的开销, 发现跨图节点间的关系, 建立质量比较好的跨图近邻边和导航边.
全局结构修复问题. 在减小合并开销的同时, 需要保证合并后的图索引具有较好的搜索质量. 这要求近邻边较为准确, 每个节点可达, 并且拥有合理的导航边. 搜索质量通过Recall-QPS曲线评价.
多索引合并问题. 有些算法适合于解决2个索引的合并问题, 但当合并索引的数目明显增加时, 应该采取怎样的合并策略.
内存效率和IO问题. 算法是否具有很好的内存效率, 降低了IO开销, 抑或是忽视了内存效率和IO问题?
并行化计算问题. 算法是否很好地支持并行化/多线程计算?
子图种类问题. 是否要求所有合并子图均为某个特定类型的图索引, 或者至少要求所有合并子图的图索引类型相同, 抑或是对于任意种类, 构造不相同的图索引也能合并.
非对称合并退化问题. 从工业场景的分段构建图索引出发, 常见的合并场景是: 一个内存中构建的小的图索引, 合并到磁盘中的巨大图索引中, 此时算法的性能是否退化.

其中1, 2, 3直接影响算法质量, 属于merge方向的核心challenge. 5, 6属于系统效率相关的challenge. 4, 7, 8属于适用范围相关的challenge.

现有方法#

以下来看现有方法如何解决以上的challenges. 以FGIM, HNSW-Merger和RNSM+MOS(以下称为MIM, 源于论文名称Multiple Index Merge for Approximate Nearest Neighbor Search)为主. 我们把问题解决的程度分成4个等级:

0: 基本没有处理

1: 涉及/提及并顺带解决

2: 有实质性的解决方案

3: 论文明确将其作为核心问题, 并提出了专用的算法, 进行了完整实验

NOTE
目前由于MIM的论文我自己读完全没有读懂, MIM的部分暂时使用AI调研的结论

复用已有结构#

FGIM#

评级: 3

cross querying中将子图已有的边加入候选邻居中, 并与跨图邻居进行比较取前k近的边. 也就是说, FGIM中复用旧边的方式是将旧边当做候选信息, 然后与新发现的跨图候选重新竞争. 注意到这个过程没有区分旧边是近邻边还是导航边, 是因为竞争时会自动保留近邻边.

HNSW-Merger#

评级: 3

直接保留了旧HNSW的邻接表. 最后与少量跨图候选一起重新剪枝. 同样不对近邻边/导航边做区分.

MIM#

评级: 2

RNSM初始化合并图时直接令点取并集, 边取并集.

也就是说，它首先保留两张原图的所有内部边。

此外，它还用源图的拓扑进行：

邻居扩展； Reverse k-NN 构造； pivot 选择； follower 分组。

因此，旧结构不仅是最终图的一部分，也是减少跨图搜索成本的工具。

但 MIM 对旧结构的判断更加依赖一个假设：

子图中原有的远程导航边已经足够好，合并时主要缺少跨图近邻边。

论文明确认为 distant neighbors 已经由各个子索引捕获，因此只需要便宜地补充其他索引中的少量近邻。

这意味着 MIM 并没有认真检查：

原导航边在全局图中是否仍然合理；是否存在大量应该替换的内部边；是否需要全局重建导航骨架。

建立跨图结构#

FGIM#

评级: 3

cross querying通过低成本的跨图kNN搜索找到全局图中该节点的k个邻居节点, 再通过kNN refinement做轻量NN-Descent找到高质量的跨图邻居.

HNSW-Merger#

评级: 3

基于假设: 一个节点的反向邻居更有可能是他的邻居, 并经过实验验证. 把原本双向的跨图搜索变为单向搜索.

MIM#

评级: 3

pivot 完整搜索 + follower 局部滑动

RNSM仍然为源图的每个节点寻找目标图邻居，但不是每个节点都从目标图全局入口开始。

Reverse k-NN 用来选择能覆盖大量邻近节点的 pivot，使大量 follower 可以直接从目标区域附近开始搜索。

它减少的是：

每次跨图搜索走到正确区域所需的距离计算

而不是减少需要处理的源节点数量。

全局结构修复#

FGIM#

评级: 3

进行了显式全局结构修复, kNNG refinement形成高质量的近邻边, 并且对于入度为0的节点, 尝试让附近节点的某个旧邻居替换为它, 避免孤立结点.

在kNNG to PG中, 使用RNG/MRNG等剪枝规则重新对kNNG剪枝和HNSW分层结构重建. 实验显示indegree repair显著降低了强连通分量数量, 提高了Recall.

HNSW-Merger#

评级: 2

进行了局部Prune剪枝, 由于旧图HNSW本身已经具有很好的导航性, 加入前向和反向候选剪枝后可以形成质量足够好的连接图. 论文通过Recall-QPS曲线证明了合并后图的搜索质量足够好. 但是没有节点的零入度保证和可达性修复. 并不能保证合并后的SCC数量.

MIM#

评级: 2

修复了分区级拓扑，没有修复向量级全局结构.

MIM在索引级图上要求图连通, 并且要求任意两个子索引在merge-order graph上相距不太远, 但是没有保证跨图边一定被剪枝保留；所有节点都能访问这些跨图桥；最终只存在一个 SCC；每个局部区域都有足够导航边。

多索引合并#

FGIM#

评级: 2

FGIM单次可以合并多张图, 但是cross querying中每个节点要对其他所有图进行k-NN搜索, 随着图索引数量增加, 这个过程的开销会显著变大, 加速收益逐渐减小. 因此, FGIM虽然可以解决索引数量比较少时的多索引合并问题, 但是没有解决当索引数量达到几十甚至几百时的合并问题.

HNSW-Merger#

评级: 3

论文提出了large-first合并方案, 指出应该优先合并最大的两个索引, 其复杂度可以得到保障.

MIM#

评级: 3

MIM没有要求把所有索引对都直接连接，也不是简单构造一棵二叉合并树。它构造 merge-order graph, 控制：

合并操作数量；

不同分区之间的最大 hop；

某个索引承担的合并负载。

内存效率和IO开销#

FGIM#

评级: 1

FGIM假定图的邻接表可以储存在内存中, 虽然邻接表的内存占用低于完整向量数据, 但是随着数据量的增大, 如1B到10B个向量数据时, 内存限制依然会成为比较大的问题. 而且FGIM也并没有解决内存不够时如何分块/流式处理以控制峰值内存的问题. 不过, FGIM在k-NNG refinement中顺带提出了DFS风格的遍历, 考虑了缓存友好性的工程问题.

HNSW-Merger#

评级: 3

HNSW-Merger提出了完整的逐层流式处理方案. 即只加载当前活动层, 流式读取目标层. 实验表明流式处理方案能够显著降低峰值内存.

MIM#

评级: 1

MIM以“大图一次性构建内存过高”为背景，主实验机器使用 512 GB DRAM，也比较了 DiskANN overlap 方案。

但是其核心算法没有给出：

有界内存执行计划；

图分块策略；

SSD 邻接表布局；

local sliding 的 I/O 复用策略；

峰值内存分析；

读写放大分析。

尤其 local sliding 要在目标图上执行大量随机图搜索。如果目标图完全位于 SSD，CPU 上减少的距离计算未必能等比例转化成 I/O 降低。

因此 MIM主要解决计算量，不解决受限内存下的执行问题。

并行化计算#

FGIM#

评级: 3

FGIM的跨图查询和大量节点更新可以并行. 论文测试了2到10个线程, 实验表示FGIM在多线程下具有较高效率.

HNSW-Merger#

评级: 3

具有完整的CPU并行方案. 论文在1到128个线程上获得近线性加速.

MIM#

评级: 2

算法本身的设计是并行友好的. 但是论文没有给出相关的具体实验结果.

子图种类问题#

FGIM#

评级: 3

FGIM的cross querying基于普通kNN搜索, 而几乎所有类型图索引都支持kNN搜索, 所以FGIM几乎可以胜任任何类型的图索引合并, 包括混合类型的图索引合并. 最后的kNNG to PG过程的剪枝适用范围也比较大. 论文通过实验测试了多种图结构, 都具有比较好的效果.

HNSW-Merger#

评级: 1

基本是HNSW专用. 论文扩展到了Vamana, 将Vamana当做单层HNSW进行合并, 并且论文认为可以类似扩展到NSG, 但核心贡献还是依赖HNSW的特殊结构.

MIM#

评级: 2

RNSM需要的基本接口是：图搜索；邻居扩展；更新邻接表；原算法的 pruning。论文分别集成到 HNSW、NSG、SSG 和 τ-MNG 中。因此它也具有较强的图家族通用性。但MIM要求输入的图是同类型输入, 没有解决混合图索引合并问题.

非对称合并退化问题#

FGIM#

评级: 0

基本没有解决. FGIM的复杂度既与小图相关又与大图规模相关, 因此在图索引大小极度不平衡的情况下, 可以判断FGIM的复杂度会发生退化.

HNSW-Merger#

评级: 3

非对称合并作为HNSW-Merger论文的重要背景, 论文很好解决了这个问题. HNSW以前向邻居估计反向邻居, 其搜索复杂度为小图规模乘以大图规模的对数, 因此对于极度不平衡的合并, HNSW-Merger能表现出很好的性能. 论文专门测试了1M与9M规模向量的合并, 取得了2.7-35倍加速. 并保持良好的Recall-QPS性能. 同时HNSW-Merger设计了逐层SSD流式处理方案, 能够完整覆盖这个工业场景.

MIM#

评级: 2

算法复杂度上与HNSW-Merger类似, 都是让小图搜索大图. 更重要的是，如果大目标图位于 SSD： pivot naive search； follower local sliding； neighbor expansion；大量目标图随机访问；都可能转化为昂贵 I/O。MIM没有提供 HNSW-Merger 那样的磁盘流式执行方案。