编者的总结

1. 本文提出的是一个预处理的方法，用于在KNN搜索中削减数据集规模，使得构建/运行其他KNN算法时内存占用变少。
2. 由于预处理后数据集变少了，那么其他算法的压缩比就可以放宽一些，精度自然而然也就提升起来了。

编者的思考

1. 本文提的算法的代价有点过高，作为一个预处理算法，有N2的复杂度，这是比较夸张的。虽然索引算法的构建和查询的内存占用少了，但是这个预处理占的资源也比较高了。
2. 核心亮点就是挖出了hubness这一度量，但是对于更为general的benchmark，即数据集数据分布和查询集数据分布未必一致吻合时，是什么情况，还有待考究。

1 INTRODUCTION

• 之前的KNN算法都是需要把整个数据集load到内存里来，这对于大数据集是不合适的。
• 无论是图的算法，还是树的算法，都对于内存开销的优化于事无补。
• 内存要想降下来，两条路，一个是向量summarazation的压缩比高一些，一个是让数据集小一些。乘积量化走的第一条路，但是精度损失较大。
• 本文走的是后一条路，删掉不重要的向量，让数据集规模降下来（比如到一半左右）。
  • 不重要，主要指的是中心度hubness，后文详细讲。
  • 其他异常检测算法，即删除异常点降低规模，本文也有考虑，在实验部分有比较，效果不如hubness。

3 WHICH VECTORS ARE UNNECESSARY?

什么是不重要的向量呢？如果给定数据集和查询集，那些数据集中不属于任何query的KNN的向量，就是不重要的向量。
本文的方法就是要删去一些不重要的向量，处理完数据集之后，任何ANN搜索算法都可以用于新的小数据集。

3.1 Hubness

首先定义中心度(hubness).节点的中心度，是指该节点包含在多少其他节点（数据集中）的KNN。形式化定义如下：

image.png
image.png

• 注意，中心度只和数据集有关，而和查询集无关。
• 中心度高的称hub，中心度低的，也就是标题中的anti-hub。
• 中心度通常用于有监督学习中，在图像检索中，hub通常是有误导性的，因为它不具备辨别性，和太多其它图像相似了，anti-hub反而是重要的。
• 但是在ANN算法中，hub反而是重要的，因为hub一般是query的KNN。

3.2 Exploratory Experiment with Deep1M

我们把查询集的KNN的所有向量构成一个集合，数据集中另一部分向量构成一个集合，分别来算中心度分布，得到如下图：

image.png

• 可以看到，中心度较低的，一般都不是KNN结果。
• 最关键的是，中心度的计算，是与查询无关的。

4 PROPOSED METHOD

4.1 Reduction of Anti-Hubs

有上面的发现，一种最简单的想法就是每个节点都算一下中心度，取前T个最大的保留就好了。

• 但是算中心度代价太高，向量两两计算距离就是的复杂度。
• 另一个问题就是，如果query是和anti-hub离得比较近的话，那么召回就丢失了。但是我们的假设是：数据集的分布和查询集的分布是类似的。那么查询也将趋向于靠近hub，数据集削减对整体的影响就没有那么大。

4.2 Approximation

上述方法复杂度太高，至少应该把距离计算的复杂度降下来。
作者的方法也非常简单：分治。
数据集首先做K-means，在每个聚类里面分别运行4.1的方法，再合并起来。

• 这样下来，距离计算的复杂度就变成了，C是聚类的个数。
• 但是这样做的代价是肯定不如之前算法的精确度要高。
• 对于300+GB的Deep1B数据集，文中取C=1000,96个线程，跑了70个小时，其中K-means花了不足40min。用GPU之后，可缩减到5个小时。

5 EXPERIMENTS

4个GPU， 3.6 GHz Intel Xeon CPU (24 cores, 96 threads) and 192 GiB内存。
python多线程写的。 k设为16.

image.png

5.5 Comparison with Other𝑁ReductionMethods

• RR是随机删数据，KNNOD是基于KNN的异常检测算法删数据，FABOD是基于角度的异常检测算法删数据。

• 删完数据之后做精确查询，召回率如图，本文的最好。

  
  image.png

5.6 Comparison with Other Reduction Methods

• 在保证内存占用（压缩效率）不变的情况下，将本文的方法和其它向量压缩方法组合使用，可以获得更高的召回。

  
  image.png

5.8 Validation of Approximation Process

• 这个实验验证K-means的近似不会损失太多。

• 可以看到，提高C，即聚类个数，对于最终召回没有太大影响。

  
  image.png