问题定义#

假设有两个向量集$X_1 = \set{x_1, x_2, ...}, X_2 = \set{y_1, y_2, ...}$, 分别有图索引$G_1, G_2$, 现在需要找出$X_1\cup X_2$的图索引$\hat{G}$.

论文希望优化三个目标:

1. 尽量降低合并已有图的成本. 也就是说, 尽量提高在全集上建图的成本减去合并已有图的成本.
2. 提高合并后的QPS
3. 提高合并后的Recall

核心观察#

作者做了一个很关键的统计实验：把数据随机切成多个子集，分别建图，再和全集直接建出的图比较。结果发现，一部分原有邻居会继续保留；同时，在全集图中新出现的边中，跨子图边通常比新出现的子图内部边更多。

以两个子图为例, HNSW 中大约有一半原邻居能保留下来, 因此, 合理的策略是: 保留旧边+发现跨图边