2012CVPR是本论文的会议版本。
本文是乘积量化技术(PQ) 最典型的索引方式。
1 INTRODUCTION
-
乘积量化技术在查询时，需要找到query对应Voroni cell或者和周边cell的点，如果数据量比较大，Cell也比较大的话，那么返回的点就会很多，需要花在Refine上的时间也会更多。因此一个迫切的要求是设计更为细粒度的分区，即vorooni cell面积更小。
-
一个最直接的方式是把codewords的个数提升一些，但是这同时意味着索引构建时间（学习时间）也更长。
-
一些索引方法也可以引入进来，比如kd-tree，tree codebooks等，但是经常会降低查询准确性。
-
本文提出的方法：多维倒排索引，在很多方面和倒排索引很相似，其优势是在不增加查询和构建时间的基础上，相比于倒排索引，能产生更细粒度的子分割（在中等大小的codebooks上）。内存消耗的增长也非常微小。
-
多维倒排索引尤其适用于大数据集上。
3 THE INVERTED MULTI-INDEX
3.1 The structure of the inverted multi-index.
- 乘积量化的核心思想就是先分段，每段分别聚类量化。
- 问题出在查询上。简单点说，现在假设就分两段，每段K个codewords，那么在PQ空间上，一共有
个聚类中心。
- 标准的倒排索引就是把这个空间划分成
image.png
- 本文的思想就是不用voroni cell，用grid，来切割PQ空间。每个轴上各格子中心点，其实就是那一组codewords聚类的中心。
-
形式化上的来讲，空间上的每一个点，都找每一段（每个轴/维度）上找和它最近的那个聚类中心(codeword)，各个维拼起来，就找到了所在的格子。
image.png
3.2 Querying the multi-index.
- 查询的时候，第一阶段分段query，分别找每一段落在轴的哪个位置上，和轴其他格子刻度的距离是多少；第二阶段是将各个轴的距离组合起来，找到最合适的若干格子用于查询。
-
注意，这里需要各段的距离可以线性叠加，或至少有公式可以计算，比如欧氏距离的平方就可以直接相加表示拼接起来的距离。
image.png
-
3.3 Inverted index vs. inverted multi-index.
- 这里的标准倒排索引，指的是不分段，直接K-means，找出K个聚类中心，用Voroni cell划分空间，共K个cell，做倒排索引的情况。
- 划分较粗；
- 列表长度基本均衡；
- 查询时，K次M维距离计算；
- 多维倒排索引，就是分成2段，每段K-means找K个聚类中心，用gird划分空间，共
- 划分较细；
- 列表长度不均衡，甚至有很多空列表；
- 查询时，每个维度K次计算，每次计算M/2向量距离，总共还是KM次计算。额外的计算量是给cell排序选TopK的计算量，但作者说这个量不大，应该确实如此。
- 内存负载额外会承担一些列表元信息，因为列表更多了，但是这个信息是很小的。数据或者数据指针二者的内存消耗都是一样的，因为数据总数是一致的。codebooks大小也是一致的。
【编者注：考虑用Voroni cell做空间划分，然后用倒排索引做索引结构的情况：此时codeboos的大小也是一样的，但是在查询时，需要额外增加次计算算出和各个聚类中心的距离，计算到每个聚类中心的距离只需要查表就可以了。内存负载和多维倒排索引是一样的。列表长度相对也会更为均衡。】
- 【论文中后面补充了一段为什么选择分两段是最优选择，不过编者没有理解，希望有理解的朋友给予指教。】
4 APPROXIMATE NEAREST NEIGHBOR SEARCH WITH INVERTED MULTI-INDEX
通过上述搜索方法得到的candidate vectors，被赋予量化后的向量和量化后的残存向量，进一步进行rerank。
本文将rerank过程进一步加速。
【编者注：有空更新】
5 EXPERIMENTS
5.1 Indexing Performance
Recall定义为1-NN准确找到的概率。
5.1.1 Candidate List Quality
T是检索的对象数。个人觉得和非PQ系列的方法对比意义有限。
image.png
5.1.2 Retrieval Speed
- 首先是红色实线和蓝色实线，之间的差距就是multi-sequence算法，可见算法复杂度比较稳定，但仍有一定影响。
- 红色线在列表长度较长时，查询时间开始线性增长。
-
作者说，标准倒排索引的速度快，很可能来自向量化实现。
image.png
5.1.3 Multi-Index + PCA
引入PCA降维之后，查询速度肯定会变快，文中没有实验。问题在于精确率会不会下降。
作者做了两种pca，一种native是直接对原始数据PCA，128维降成32维；另一种是分PQ-aware是分两段分别PCA再拼起来。
可以看到PQ-aware-PCA对准确率影响很小。
image.png
网友评论