标题：通过优化的有指导搜索和贪婪算法实现近邻图上的两阶段搜索
作者来自杭电

编者的总结

1. 本文将图上的贪婪查询分为两阶段，第一阶段导航重点在效率，第二阶段搜局部近邻重点在精度。
2. 分别为两阶段设计了优化算法。第一阶段将每个点的邻居分区；第二阶段搜二跳邻居作为精度补充。

编者的思考

1. 两个查询阶段的时间代价比例没有给出来，据编者的实验经验来看，第二阶段往往占据着更长的时间。因此导航阶段的作用可能较小。
2. 缺少消融实验。如果把TOGG的第一阶段换成HCNNG的guided search，性能会有降低吗？
3. 两阶段之间的衔接不太明确。本文是第一阶段收敛后用第二阶段补充，这意味着local neighborhood其实已经搜了个大概了，此时衔接第二阶段可能意味着重复计算。或者某些点已经被顶替掉了，精度也无法补充。

ABSTRACT

• ANNS的贪婪搜索过程分成两个阶段，第一个阶段距离query较远，为导航阶段；第二个阶段和query比较近，为精度搜索阶段。
• 第一阶段主要关注导航效率，第二阶段主要关注搜索精度。
• 现有的贪婪搜索方法，在第一阶段效率较低，第二阶段容易陷入局部最优。
  • 如下图右上方，在导航阶段，很多非query方向的邻居其实没必要去搜；
  • 在第二阶段，贪婪算法容易陷入局部最优

image.png

• 现有方法比如HCNNG中的guided search，只挑选query方向的邻居，在第二阶段极易陷入局部最优；
• learning的方法会为每个点再多学一个表示，虽然对局部最优有缓解，但是训练代价太大，且会引入额外内存开销。

3. Two-stage routing strategy with optimized guided search and greedy algorithm

本文的方法是将两个查询阶段分开考虑，导航阶段专注于快速导航，精度阶段限制局部最优。

3.3. Optimized guided search

快速导航阶段作者提出了两种方案，一种是将邻居做kd-tree，一种是将邻居做k-means。

3.3.1. Optimized guided search based on modified KDT

• 首先将各维度按照值域分成等宽的grid；
• 对于每个节点，把邻居分成三份，在当前grid的，在左侧grid的以及右侧grid的。
• 每个维度有一种分法，选择其中最均匀的分法
• 这就形成了一个三叉的kd-tree，搜索时只选择一部分即可。
• 这个kd-tree最终实际只有两层，分了一次。作者表示，分的次数多了也会影响性能。

3.3.2 Optimized guided search based on KMC

很显然，kd-tree只考虑了一个维度的差异，因此作者设计了k-means将邻居聚类。但是k-means的路由也需要和多个聚类中心进行计算，路由代价比较高。

3.4. Optimized greedy algorithm

为了避免局部最优，在第二阶段中，candidate set中的点，不仅检查其邻居，其邻居的邻居也会做检查。

3.5. TOGG routing process

整体搜索算法如下，先用第一阶段算法运行到收敛，然后将candidate set全部置为unvisited，然后用第二阶段算法补精度。

5. Experiments

• 数据集如下

  
  image.png

• 度量指标speedup如下：相比于暴搜的距离计算次数，节省的比例

  
  image.png
• baslines: 全部是图上查询路由的算法
  • kdd'11: 基于radius search的算法
  • cvpr'16: backtracking回溯算法
  • pr'2019: hcnng guided search算法
  • tpami'21: 普通贪婪算法

5.2. Comparing with prior routing strategies

• 范围查询和回溯的搜索空间太大，导致低精度需求或者数据集偏简单或者k的值比较小时难以奏效；
• kd-tree比k-means好像还好一些，比较反直觉，作者没有解释，可能导航时的需求不大？

• 性能提升幅度不大

  
  image.png