2015TPAMI(IMI多维倒排索引)-The Inverte

2022-06-17 本文已影响0人 Caucher

2012CVPR是本论文的会议版本。
本文是乘积量化技术(PQ) 最典型的索引方式。

1 INTRODUCTION

乘积量化技术在查询时，需要找到query对应Voroni cell或者和周边cell的点，如果数据量比较大，Cell也比较大的话，那么返回的点就会很多，需要花在Refine上的时间也会更多。因此一个迫切的要求是设计更为细粒度的分区，即vorooni cell面积更小。
一个最直接的方式是把codewords的个数提升一些，但是这同时意味着索引构建时间（学习时间）也更长。
一些索引方法也可以引入进来，比如kd-tree，tree codebooks等，但是经常会降低查询准确性。
本文提出的方法：多维倒排索引，在很多方面和倒排索引很相似，其优势是在不增加查询和构建时间的基础上，相比于倒排索引，能产生更细粒度的子分割（在中等大小的codebooks上）。内存消耗的增长也非常微小。
多维倒排索引尤其适用于大数据集上。

乘积量化的核心思想就是先分段，每段分别聚类量化。
问题出在查询上。简单点说，现在假设就分两段，每段K个codewords，那么在PQ空间上，一共有 $K^2$ 个聚类中心。
标准的倒排索引就是把这个空间划分成 $K^2$ 个Voroni cell，查询时query在哪个cell就定位即可。如下左图（两维数据），但是会产生一些边界问题，也容易产生倾斜问题。

image.png

本文的思想就是不用voroni cell，用grid，来切割PQ空间。每个轴上各格子中心点，其实就是那一组codewords聚类的中心。
形式化上的来讲，空间上的每一个点，都找每一段（每个轴/维度）上找和它最近的那个聚类中心(codeword)，各个维拼起来，就找到了所在的格子。

image.png

查询的时候，第一阶段分段query，分别找每一段落在轴的哪个位置上，和轴其他格子刻度的距离是多少；第二阶段是将各个轴的距离组合起来，找到最合适的若干格子用于查询。
- 注意，这里需要各段的距离可以线性叠加，或至少有公式可以计算，比如欧氏距离的平方就可以直接相加表示拼接起来的距离。
  
  image.png

这里的标准倒排索引，指的是不分段，直接K-means，找出K个聚类中心，用Voroni cell划分空间，共K个cell，做倒排索引的情况。
- 划分较粗；
- 列表长度基本均衡；
- 查询时，K次M维距离计算；
多维倒排索引，就是分成2段，每段K-means找K个聚类中心，用gird划分空间，共个cell，做成倒排索引。
- 划分较细；
- 列表长度不均衡，甚至有很多空列表；
- 查询时，每个维度K次计算，每次计算M/2向量距离，总共还是KM次计算。额外的计算量是给cell排序选TopK的计算量，但作者说这个量不大，应该确实如此。
- 内存负载额外会承担一些列表元信息，因为列表更多了，但是这个信息是很小的。数据或者数据指针二者的内存消耗都是一样的，因为数据总数是一致的。codebooks大小也是一致的。

【编者注：考虑用Voroni cell做空间划分，然后用倒排索引做索引结构的情况：此时codeboos的大小也是一样的，但是在查询时，需要额外增加 $K^2$ 次计算算出和各个聚类中心的距离，计算到每个聚类中心的距离只需要查表就可以了。内存负载和多维倒排索引是一样的。列表长度相对也会更为均衡。】

通过上述搜索方法得到的candidate vectors，被赋予量化后的向量和量化后的残存向量，进一步进行rerank。
本文将rerank过程进一步加速。
【编者注：有空更新】

Recall定义为1-NN准确找到的概率。

T是检索的对象数。个人觉得和非PQ系列的方法对比意义有限。

image.png

引入PCA降维之后，查询速度肯定会变快，文中没有实验。问题在于精确率会不会下降。
作者做了两种pca，一种native是直接对原始数据PCA，128维降成32维；另一种是分PQ-aware是分两段分别PCA再拼起来。
可以看到PQ-aware-PCA对准确率影响很小。

image.png