编者的总结

1. 本文最大的贡献在于理论证明。放松裁边规则，相比如RNG裁边，引入适量更多的边，可以降低查询复杂度，这个结论很重要。
2. 基于强证明的近似提供了一个方法，在1M数据集上也有提升。
3. 有一个基于余弦定理的优化很有意思，效果很好。

编者的思考

1. 理论证明还是没有扩展到kNN的情况，另外理论上的那个强图没有任何实验验证其结论。
2. 最后本质上就是在通过参数调整裁边的松紧程度，相比于理论证明要逊色一些，有点match不上，且实际用起来也会很麻烦，调整的过程引入很多参数。
3. 方法的动态插入和删除挺麻烦的，而且没有实验。
4. 最后的提升是不是主要是余弦定理和early stop两个优化点提供的呢？

1 INTRODUCTION

目前图方法对于理论复杂度方面有两个极端的假设：

• 一方面有些工作假设query在数据库里面，比如MRNG(NSG的精确版)，这显然不一定成立；
• 另一方面有些工作对query和NN的距离完全不做假设，比如DG,HNSW,SSG等，这样要不然没有Error guarantee，要么是个线性复杂度。
• 作者推荐的是把这个距离的上界预定义一下，基于此做复杂度分析。之前FANNG做过这件事情，但是查询复杂度做的太高了。

image.png

• query和NN距离上界的合理性，作者用两个预实验来说明。

• 第一个实验想说明这个距离一般不大；

• 第二个实验说明NN和其他点的距离差很大。

  
  
  image.png

• FANNG复杂度过大的问题在于greedy routing每一步保证前进的距离太短，仅为数据集中距离最近的两个点的距离。

• 本文的方法-MG的核心就是一个新的裁边规则
  

  image.png

• 这样的裁边规则可以保证，只要query和NN的距离不超过，从任一点出发，每一步的进步不会小于。

• 为了减少构建复杂度，对-MG做了一个近似-MNG；并且在其上使用beam search提升精度，且提供了一个优化方案能做一些剪枝。

3 PRELIMINARIES

3.2 Proximity graph

• MRNG是月牙形裁边，在月牙内的点可以驱逐月牙边的点，即120度内不能有更短的边。
• MRNG很好的性质是只要query在数据库内，从任意点出发肯定可以找到NN。

• 但是如果不再数据库内，比如图b，greedy search就找不到它

  
  
  image.png

4 ANALYSIS OF THE INEFFICIENCY OF EXISTING PROXIMITY GRAPHS

本节证明了现有PG greedy routing的期望长度为

是数据库中两个点的最小距离，可以证明
的概率至少为

则可以推导出，greedy routing的期望长度在此概率下，不小于

当n比较大的时候，->0，证明普通PG在数据集较大时查询速度会变得很慢。

5 𝜏-MONOTONIC GRAPH (𝜏-MG)

• 裁边规则：即如上图c所示，uu''无法驱逐uv，灰色环内的点和u连边都可以和uv共存，月牙禁区变小了，裁边弱了一些。
• 𝜏-MG：有向图，服从两个定义
  1. 任何距离不足的两个点，必然双向相连；
  2. 如果两点距离大于且没有相连，那必然是被一条其他的边驱逐了。
     • 反过来说，如果没被驱逐，则一定相连。
• 单调性：𝜏-MG对于任意一个query，只要其NN和Query的距离不足，一定存在一条单调路径从query到NN，每一步步进超过，除了最后一步。

5.1 Construction of 𝜏-MG

• 基本思路是先建MRNG，再补边。毕竟𝜏-MG是MRNG的裁边放松版本。
• 具体算法也很粗暴，建好MRNG之后，遍历所有其它的点，如果距离不足，直接补边，否则看目前是否有边能驱逐该边，没有的话也补进来。
• 边的出度期望可以证明是的，注意MRNG的边的度数期望是常量的。
  • 这个O(lnn)的来源是一个点的密度是O(lnn)的假设
• 最终构建的复杂度仍然是，和构建MRNG的复杂度一样，但是常量倍数肯定不一样了。

5.2 ANN search on 𝜏-MG

• greedy search算法有修改，每次先尝试找距离以上的和query最近的邻居，如果这些邻居都更加远离query，那么再找距离以内的邻居。
  
  image.png
• 这样的搜索方法基于一个定理，就是如果以外的邻居如果都更加远离query，那么最近邻就在以内了。
  • 换句话说，𝜏-MG的greedy routing保证能搜到NN，但Qurey和NN的距离不能超过。

5.3 Update of 𝜏-MG

对于𝜏-MG似乎支持起来比较困难，每次插入需要计算和所有点的距离。

6 𝜏-MONOTONIC NEIGHBORHOOD GRAPH (𝜏-MNG)

6.1 Construction of 𝜏-MNG

𝜏-MNG是𝜏-MG的近似，目的是加速构建。
构建方式和𝜏-MG也是类似的，但有以下几个区别：

1. 从空图开始构建，并非从MRNG再refine补边；
2. 需要建一个HNSW或者NSG辅助构建；
3. candidate neighbor list从HNSW获得近似h-NN，而并非全部数据集。

image.png

这种近似方式构建复杂度肯定是降低了，但是error guarantee也没了。

6.2 ANN search on 𝜏-MNG

之前𝜏-MG的搜索算法没法再用了，因为不保证有单调性了。只能再把经典的search算法拿出来。

image.png

作者为经典beam search在𝜏-MNG的Error guarantee给了一个弱保证，即如果beam size足够大，beam serach找到NN的概率不低于进入neighborhood的概率。
进入neighborhood即beam search访问过query的近似h-NN，也是一个模糊定义。
总之最终是要调beam size的。

6.2.1 Optimization for the search algorithm

• 这是一个启发式的idea，离得比较远的点，它的邻居普遍也离得比较远，因此可以少算点。如下图，如果当前点不在candidate list的前p%中，那么我们首先给它的邻居算一个下界距离排个序，然后只对前p'%的邻居算真实距离，后面的不算了。
• 这不是一个精确的剪枝方法，只是一个启发式优化。

image.png

• 下界距离的定义也很简单，欧氏距离只算一部分，但会把占比较大的维度提前放置，具体来说就是先离线做下SVD，用SVD的前几维来计算。

  
  
  image.png

6.2.2 Implementation details

两个优化技术：

• Partial distance-based pruning (PDP)：距离算一半如果可以提前剪枝掉就不要再计算了；
• Prefix inner product index (PII)：用余弦定理计算距离，可以减少一半计算量，但需要为数据库中每个点提前计算模长并存储。
  • 为了和第一条优化技术相结合，可以分段计算，但也会加大存储量。

6.3 Update of 𝜏-MNG

插入支持的比精确图要好一些。先近似搜索candidate neighbor list，然后裁边。但是需要周期性重建。

7 EXPERIMENTAL EVALUATION

image.png

7.1 Comparision with the baseline methods

• 小数据集上还不错，提升比较稳定

  
  
  image.png

7.2 Effect of 𝜏

这个参数是个trade-off，首先越大，对RNG裁边的放松越多，就意味着边越多。先放松一些，补充一些边，可以提高连通性，降低复杂度；再多补边，每一步查询代价就变大了。

image.png

7.3 Performance of QEO

这个下界剪枝提升一般，且不稳定，参数也不大好调；

image.png

7.4 Performance of PDP and PII

early abandon 和 余弦定理看起来很管用。

image.png

7.5 Comparison of index size

index size还是变大了一些的，毕竟放松了裁边规则。

image.png

7.6 Performance against dataset size

分成若干份10million的数据集，然后顺序查找，最终汇总。可以看到是一个线性的复杂度。而且为了提高到0.98所需要的代价则更高。

image.png