本文作者来自丹麦和意大利，曾设计ann-benchmarks获得ANN领域广泛关注。
编者的思考
- 只选了数据集中的点当做query，可能会有bias。
- LID, expansion, RC和图索引算法的设计逻辑并不匹配，包括最终的评估效果也一般，文章没有提供强有力的结论。
- 平均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和距离数据集中其它所有点的均值的比值。
- LID: 给定一个点q, 和一个距离r，LID描述了区分距离q, r和(1+
-
实验包括两组：
- 固定一个数据集，根据三个度量将Query分成easy, middle, hard三组，观察实际查询性能的区别。【LID表现不错】
- 观察不同的度量值分布，在不同数据集上如何影响运行时间分布。【任何一个度量对实际性能分布的预测都不准】
- 其中，第一组实验用了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
网友评论