标题：HVS：基于泰森图的层次化图结构解决近似最近邻搜索
作者来自日本名古屋大学，大阪大学和北海道大学

编者的总结

1. 本文的核心思路是把HNSW的上层替换掉，做一个收敛到query neighborhood速度更快，质量更好的起始位点，以达到更好的查询速度。
2. 多层PQ图的这个思想很有趣，某些voroni cell中包含的数据点很密就到下一层用基数更大的Voroni cell细分，这实际上是解决了PQ中的一些数据倾斜的问题，采取的是自适应PQ分段的思想，最终达成的效果就是基于数据密度做分区。

编者的思考

1. 之前有研究（https://www.jianshu.com/p/580609371bed）提出HNSW的上层结构提供的快速导航不是查询bottleneck，因此用处不大；而本文的核心提升就在快速导航阶段以及入口点的选择，在某种程度上是不是一种冲突？或者是否可以理解为，只要导航最终得到的入口点足够好，仍然能有效提升查询性能？
2. 如果上层的收敛质量足够好，那么在底层的查询将只是在query neighborhood的局部进行查找，这时使用局部性质更好的KNN图会不会效果更好？
3. 这个工作一个弱点是没有理论保障，不能确定找到的enter point和query point的距离是不是足够近（比如前1%近的点）。复杂度的分析也建立在了错误的基础上（HNSW的搜索复杂度是O(logn)的说法是经不起推敲的），构建的复杂度也没有分析。
   ps: 尽管如此，这份工作的质量已经足够高了
4. 实验仍有不少疑点；
5. 另外一个感受是，partition-based的方法，比如PQ，也能够快速达到local neighborhood，本文的一个深层思想，其实就是先用partition的策略快速到达高质量的local neighborhood，再用图结构完成高精度搜索。

ABSTRACT

快速接近query neighborhood以提升搜索性能

3 THE CONSTRUCTION OF HVS

3.1 Basic ideas

如下图，HVS的主要结构分成三部分：

• 第一部分是top layer，这一层没有边，只有一些node，但不是数据集中的点；
• 第二部分是从second layer到bottom layer这些中间层，有一些node，node之间有边相连（以HNSW的方式连边），每个node会对应一个真实数据点作为代表；
• 第三部分是base layer，就是HNSW第零层，每个node都是真实数据点。

从top layer到base layer，从上往下会有一些跨层的边，只有这些边能负责跨层的路由。第一部分和第二部分在查询时负责找base layer的入口点，HVS的核心竞争优势就是有一个更好的入口点。

image.png

上面提到，第一部分和第二部分的图中node不是数据集中的点，具体来说：

• 在bottom layer，会做一次PQ，PQ的centroids就是图中的node；这一次PQ选的段数会很多（即codebook个数很多），之后上层图通过将两段合一不断将codebooks个数减半（每个codebook的size保持恒定，即codewords的个数，等同于PQ做k-means时中心点的个数）来让图中的node个数向上层快速衰退。
• 也就是说，上层的node一定属于下层；
• 但是，这和实际的PQ不是一回事，得到的图也很称之为Voroni图；如果在上层按照一半的分段数和相同的codewords个数进行PQ，得到的codewords大概率下层中没有，所以才采用了在bottom layer做PQ，自底向上合并的策略。

image.png

上面一直在讲各层的node和图，那么数据集本身的点是如何索引的？

• 与node相反，数据点不在top layer出现，且自上而下一层比一层少（子集关系），到bottom layer点是最少的。
• 其原因是：在second layer, Voroni cell的基数很少，很多cell内的密度都很高，这些高密度cell会继续传递到下层，在下层用更大基数的voroni cell再进行划分。

3.2 Multi-level quantization technique

本节主要讲上层的node是怎么选出来的。

1. 首先在第T层 (bottom layer) 做一下PCA-OPQ，结果需要保留一个旋转矩阵，和个codebooks。
2. 自底向上选择上层的nodes。具体来说，每次要对下层的codebooks两两配对准备合并（即，向量的两个小段合并成一个大段），假设每个codebook有L个codewords，一对codebook就可能有种可能的codewords，我们还需要从中选出来L个。
   接下来我们针对这两个问题给出答案

如何两两配对codebook？

如下式，作者使用互信息来评价一对codebook，其中代表y在C上的密度，定义为数据集中点落在y的cell里的比例，比例越高密度越大。

image.png

• （编者注：这里不清楚具体是怎么算的，推测可能是和组合起来的子空间上，按照个codewords分割子空间，再用数据集投影到这个子空间上算密度）
• 那到底是互信息大的配对好还是小的配对好呢？作者想到PQ能更好处理熵值大的数据，因此就选择互信息大的了。
  (编者注：这里感觉比较难说，因为这里定义的密度他不是熵，也不是信息量，而组合起来太密有可能不是好事。综合下来这里的这个东西有可能不重要，感觉就算随机拼凑一下组合也未必效果就差，有待验证。)
• 由于找一个全局最优的组合很困难，是一个NP-hard的问题，所以也就贪婪算法了，每个codebook找一个局部最优的而已。

• 在找到结果之后，每一层留一个旋转矩阵就可以了，代表各个段的最终位置。

  
  image.png

如何选择L个codewords？

上面提到，合并两个codebooks需要从个codewords中选择L个最合适的。作者将这个codewords做了个带权K-means，然后把聚类中心移动到最近的codewords即可。如果有重复，就再用一个“重要性采样技术”去生成剩下的几个。
（编者注：感觉怎么选可能也不是很重要）

实现细节

• top-layer固定分4段（按照文中的符号就是在第二层），然后每个codebook中的codewords个数 (L) 固定为16。
• second layer不是分8段，而是分16段，按照文中的说法就是第4层。在这一层L=256，已经可以对大部分点做一个很好的近似了。
• 在每一层的每个voroni cell，会从这一层的数据集中（下一节讲如何选）找到在voroni cell的一个数据子集，如果子集为空，这个cell对应的node直接丢掉，不参与建图；不为空的Cell要选择一个数据子集中和node最近的点称作代表点。
• 跨层的边：起点是一个voroni cell，终点是base layer的一个点，或者是下层的一个seed point。
  • 如果一个Cell中的所有点都中止在这一层，那这个cell直接连到base layer的表示点上；
  • 否则的话，找到这个cell里的，离seed point最近的那个非中止的数据点，找到在下一层包含这个点的voroni cell的seed point，构建一条从当前Cell到这个Seed point的跨层边。
  • 比较特殊的是top layer的点，它们直接在second layer上去找10-NN，然后从top layer的seed point构建10条边指向这10个second layer的seed point。

3.4 Density-based data allocation strategy

这一节讲如何逐层对HVS赋予数据点。首先要明确的是，base layer包含全部数据点，top layer不包含任何数据点；second layer包含全部数据点（文中未明说）。我们接下来讲的是从3-rd layer开始，逐层筛选数据子集的过程。

什么样的数据点会继续进入到下一层，接受更严格的PQ空间分区呢？答案是那些在当前层的voroni cell密度过大的点，如果一个voroni cell挤进去太多数据点，实际上数据分割和近似效果就会差一些。具体来说，本文使用的评价指标是knn的密度估计乘量化误差。密度估计如下式，是从一本书中学来的一个方法，有一定道理但也有强假设。

image.png
有了指标之后，每次会选择指标最大的那一批数据点进入下层，每次选的数据量进入下层，整体就会是指数衰退的。

4 THE SEARCHING IN HVS

• 由于上层的codewords都是bottom layer的codewords的组合，所以query到来时，只需要在bottom layer算出和各个sub-codewords的距离就可以了，这样和整个上层结构的距离计算都可以很快完成。
• 在这之后，top layer的最近邻可以直接暴力计算找出来（有distance book的帮助），然后逐层按照跨层的边来进行搜索。
• 在每一层，都执行标准Best-First-Search搜索算法，实质上是在seed point上进行搜索，找到一组较近的seed points和对应的voroni cells，然后通过跨层边进入下层。
• 最终在bottom layer，会有一组enter points (数量是多少是个重要的查询参数)。从这组enter points开始在底层HNSW查询。

6 EXPERIMENTS

Intel(R) Xeon(R) Gold 6262V CPU@1.90Ghz with 200GB memory, running in Ubuntu 18.04.
C++编写

• 参数设置方面，在低维数据集上，ImageNet, Tiny80M，上层的层数T设置为4，也就是只有top layer和second layer，分配策略直接没用。
• 在GIST上T=6，除去top layer后有三层，
• 其他三个数据集上，T=5，
  image.png

6.2 Memory cost

• NSG和NSSG的出度很大，因此内存占用量比HNSW还要高
• NSG在Glove和Tiny80M上出度太大，作者认为这是不Scalable的，编者对此质疑，因为很多论文都复现了实验，没有出现相关问题。

• HVS-HNSW比HNSW多在了seed points上，应该也就是每一层的codebooks，编者对此质疑，旋转矩阵R，seed point的代表数据点，数据点存在的层数也会占用内存。

  
  image.png

6.3 Indexing time and training time

• 结果显示HVS似乎是构建最快的，原因是它的efconstruction比HNSW选的要小（500 v.s. 1024)，能选的比较小的原因是上层图质量比较高。

• 上层图的构建速度上，作者说得益于distance book可以构建的比较快，HVS的上层构建也比较快。
  （编者对此将信将疑，一方面从论文中看上层seed points的选取，即合并codebooks，选L个codewords，复杂度应该不低；另一方面数据集自顶向下过滤也要过滤好多遍，每一轮的复杂度（knn密度估计）也不低，训练时间真的这么短吗？）
  （编者：NSG和NSSG放在这里似乎很鸡肋，NSG和NSSG本来主打的就是构建速度，这个结果可以说和原文出入很大，是不是参数有问题？）

  
  image.png

6.4 Search performance

6.4.1 The efficiency of multiple levels.

• 层数越多，搜索性能越好；
• 和1的性能差不太多，证明的是那个数据集向下过滤的思路是有效的。
  image.png

6.4.2 The comparison study

• 整体搜索性能有提升；

• NSG和NSSG相比于HNSW也普遍好一些

  
  image.png

• 在前期快速导航方面有优势

  
  image.png

• range search也有优势

  
  image.png