倒排索引在亿级向量数据近似最近邻搜索下的优势（IVF-HNSW）

简介

论文题目：Revisiting the inverted indices for billion-scale approximate nearest neighbors，2018年发表在ECCV会议上。论文在分析inverted index在大规模数据上的优势（vs. IMI）并借助proximity graph （HNSW）缓解其不足，在billion-scale数据上实现更优ANNS。

主要内容

提出grouping和pruning策略优化inverted index，提升压缩精度和查询召回率。grouping策略将聚类得到的区域进行细分，得到更小的区域并利用PQ压缩；在grouping基础上，pruning可实现更细粒度的定位。通过HNSW定位最近的几个区域（聚簇）

动机

倒排多索引（inverted multi-index, IMI）是一种有效的亿级数据检索方案。但IMI存在问题：IMI划分的很多区域没有数据点，导致有效区域数量较少，可能引起搜索花费大量时间在空区域。本文认为这主要由于IMI为不同的子空间 独立 学习码本，然而实际上不同子向量（子空间）并不是统计独立的，不同子空间之间可能是非常相关的（比如，CNN产生的descriptors）。

当前对IMI（或PQ）的优化研究大都提升了召回率，但他们的运行时间普遍为10ms左右，在实际场景中还是比较慢。

IMI vs. inverted index

IMI的优点：（1）精确的候选列表；（2）索引和查询效率高。（在码本尺寸K较小时）

缺点：但在K超过

2 14 2^{14}

2

1

4 之后，随着K的增加，IMI的性能提升很小。存在大量随机内存访问；内存消耗大。

inverted index的优点：（1）搜索时随机内存访问少；（2）随着K增加，性能提升大；（3）内存可扩展性好；

缺点：对应IMI的优点。

因此，在billion-scale数据上，inverted index更有潜力。

论文的方法

grouping

把原始inverted index中的一个区域（聚簇）划分为多个groups（即更小的区域或聚簇）。朴素方案是对区域里的点再聚类划分，本文通过目标区域中心与邻域区域中心联合提出更好的划分方案（AnalyticDB-V也采用了类似方案，VLDB2020）。然后，在小区域上执行PQ压缩。

pruning

就是在小区域上通过与相应小区域中心距离评估剪枝掉较远的小区域。

实验结论

（1）inverted index在billion-scale数据上更有潜力，有更多优化空间。

（2）本文内容其实就是执行了两层的划分，第一层是原始的k-means聚类，第二层是作者提出的新的划分方案。