背景
ANNS 索引的类型:
- 树索引
- 哈希索引
- 图索引
- 基于量化的索引
一个简单的图索引为k-NN图, 即每个节点与其k最近邻节点连边. 但k-NN图有一些问题: 容易造成冗余边, 缺少绕出局部区域的边.
图索引根据构建方式可以分为以下几类:
- 分治构建: 构建子图, 然后合并各个子图. ELPIS(CPU), SPTAG(CPU), GGNN(CPU)
- 增量构建: 逐渐向图索引中插入向量. NSW(CPU), HNSW(CPU), GANNS(GPU)
- 优化构建(refinement): 先构造近似k-NN图, 然后剪掉冗余边. NSG(CPU), Vamana(CPU), CAGRA(GPU)
文章主要聚焦于refinement-based构建方式(文章认为, 增量构建由于需要顺序插入节点, 不适合并行化). refinement-based构建方式分两步: 构建一个比较稠密的近似k-NN图(k-NN graph initialization), 再从候选边中剪掉冗余边(graph pruning).
文章认为现有方案CAGRA主要有以下几个问题:
- GPU版NN-Descent后期收敛慢
- 不同的剪枝策略无法统一设计加速框架, 有些剪枝策略需要进行串行计算.
- 1B量级下, 内存占用过高, 这需要GPU-CPU-磁盘协同工作, 导致过多的磁盘io, 降低了性能.
于是文章提出了Tagore:
- 引入GNN-Descent算法(两阶段)
- 提出CFS框架(三阶段: 收集候选邻居, 剪枝过滤, 储存优化邻居)
- 为CFS框架开发了两个GPU内核(1. 并行增量内核; 2. 并行平衡内核)
- 针对大规模数据集设计了异步GPU-CPU-磁盘框架.
NN-Descent算法补充注意到暴力计算k-NN图时间复杂度过高. NN-Descent的核心思想是只计算少量的点对, 得到高质量的近似k-NN图.
近邻具有传播性, 我的近邻通常来说也是我的近邻的近邻. 对于某个节点来说, 先随机指定一些近邻, 然后查询该节点近邻的近邻, 进行松弛操作, 迭代若干次后得到近似k-NN图.
- 随机初始化. 每个节点随机选择k个节点作为初始邻居
- 生成候选: 假设N[u]表示u的邻居集合. 对于N[u]中的每个邻居i, 将N[i]加入候选集合.
- 更新邻居表: 对于候选集合里的每个j, 计算d(j, u).
- 取已有邻居和所有候选中的前k大距离.
- 不断迭代. 直至几乎没有新邻居加入.
我们发现以上算法枚举每个节点为起始节点, 然后找到其近邻的近邻, 这非常慢, 因为每条边会被反复遍历. 我们可以转换枚举对象, 枚举中间节点, 考虑其候选点1和候选点2之间是否可以更新, 容易发现转换枚举对象后每条边只会被遍历两次.(local join) 但是需要注意枚举中间节点A的话, 我们不能只枚举A的邻居, 还要枚举”以A为邻居的节点”(反向邻居), 因为在k-NN关系中近邻关系不一定是对称的.
我们需要迭代多次, 会发现有些距离会被反复计算, 于是我们把每个节点的候选表换为两个候选表: new表和old表. new表储存新加入还未计算距离的候选节点, old表储存已经计算过关系的候选节点. 每次只对new-new和new-old关系进行计算即可.