本文作者来自丹麦和意大利，曾设计ann-benchmarks获得ANN领域广泛关注。

编者的思考

1. 只选了数据集中的点当做query，可能会有bias。
2. LID, expansion, RC和图索引算法的设计逻辑并不匹配，包括最终的评估效果也一般，文章没有提供强有力的结论。
3. 平均recall，和平均query time，都隐藏了很多实际性能分布，不适宜作为benchmark的度量。

Abstract

• 本文提出的LID, RC, query expansion三个度量，可以为现实数据集选择各种难度的query。
• 调查了目前常用的多个数据集，发现并不是很多样，在一个数据集上的结果往往能代表在其他数据集上的结果。

1 Introduction

• 很多数据集不是真正高维的，即可以通过一些手段把数据集映射到低维，使得数据间的距离不会有太多失真。

  • 本征维数(ID)就是允许有这样性质的最低维度。
  • JL转换，PCA，都可以用作低维嵌入的实际手段。

• 本文重点关注维度的局部度量方式，即局部本征维数LID, query expansion，和Relative Contrast (RC)，以及它们如何影响了查询性能。

  • LID: 给定一个点q, 和一个距离r，LID描述了区分距离q, r和(1+)r的点的难度。
  • expansion：描述了knn和2knn到q距离的比值。
  • RC：1NN和距离数据集中其它所有点的均值的比值。

• 实验包括两组：

  1. 固定一个数据集，根据三个度量将Query分成easy, middle, hard三组，观察实际查询性能的区别。【LID表现不错】
  2. 观察不同的度量值分布，在不同数据集上如何影响运行时间分布。【任何一个度量对实际性能分布的预测都不准】
  • 其中，第一组实验用了qps-recall curve来表征，但作者认为平均recall会隐藏很多insights。
    • 比如说，对于图索引来说，查询精度的方差特别大，而对于其他类型的索引方差就会小很多。
  • 最后，作者想要选出一组代表性数据集来benchmark各类索引。然而现实benchmark中的数据集多样性很差：各索引排名基本一致，但各索引在不同数据集上性能表现不同。

4 Datasets

• 下图是在三个度量上的各数据集直方图（以数据集中点当做query），k=100。均为偏态、长尾分布，Expansion是log轴。

• 从后面的结果来看，各个度量的中位数将数据集难度排名，和实际性能排名基本一致，但有两个例外：LID和Expansion预测错了SIFT和Glove的顺序，RC弄错了MNIST。所以都不太能预测的准。

  
  image.png

• 三个度量的相互关系：相关性并不强

  
  image.png

• 根据LID，各选了10000个Easy, middle, hard的点当做query

• 从定性上来看，LID能选出更难的Query来

  
  image.png

• 固定算法为Annoy，一个随机映射树索引，比较三种度量对query的选择性

  
  image.png

• 固定Recall为0.9，查看不同难度query set的性能下降比例

• LID下降的最多

  
  image.png

• 再次固定算法为Annoy索引，LID为度量，点状虚线是middle的，实线是diverse的，middle要比diverse更难。作者解释实际上这些索引达到高Recall是通过让Diverse中的简单query精度打满，而非提升难Query的精度。

• 另外，Fashion-MNIST虽然在分类难度上远大于MNIST，但是ann的难度上却差不多。

  
  image.png

5.4 Diversity of Results

• 用LID选出来的middle query set做benchmark。
  【为什么不用diverse呢？】

• NDC和QPS排名差距很大，这点很奇怪。

  
  image.png

5.5 Reporting the Distribution of Performance

• 各种索引在glove-2m数据集上的性能，但不仅仅是Recall-time curve，对于每一个点，都画了关于横轴的分布（上图是各点recall的分布，下图是各点的QPS的分布）

• 下面这组图中，IVF和Annoy峰度很高，说明对所有query的NDC差不多，方差很小，其余三个则展现出双峰形态。

  
  image.png

• 固定ANNOY和glove-2m数据集，（也许固定了ndc？），画出recall和measure的格子图，都一般。

  
  image.png