标题：HD-Index：将高维空间近似KNN搜索的“可伸缩性-精确性”界限再推进一步

编者的总结

1. 本文第一个贡献在于维度分区，通过希尔伯特降维，构建B树；
2. 本文第二个贡献在于引入度量空间中的Reference points和距离三角不等式，在B树中存储与锚点的距离。

编者的思考

1. 索引大小太夸张了，作为一个disk-based的，非物化的索引，大小居然和HNSW差不多，甚至还要超出去一些，这实在难以接受。
2. 正如作者提到的，极高维情况下，B+树会搞的太多，导致无法处理。
3. 文章的算法整体表现中庸，但是把AI-domain的方法拉向了现实一些。

1. MOTIVATION

• LSH方法构建索引时需要的空间太大，因此不具备可伸缩性。SRS是这一类最好的方法。

• 第二个就是近似比例，如下定义，近似比例的提升未必一定会导致MAP的提升，不是绝对相关的。

  
  
  image.png
  
  
  image.png
• 第三个是说空间填充曲线是存在假阳性的。在空间曲线中相近的，真实空间中距离不会远；反之，在真实空间中相近的，空间曲线中可未必相近。
• 第四个是说B+树对于size比较大的数据类型比较矛盾，存指针则必然随机IO，存数据则导致叶子节点剧多，IO效率下降，B+树高度增加。

3. HD-INDEX CONSTRUCTION

对于高维数据，首先将维度分割成若干分区，每个分区通过希尔伯特曲线降维成1维，RDB-tree对这个1维数据进行索引。RDB-tree上层就是B-tree，叶子节点存的略有不同。

3.1 Space-Filling Curves

• 维度分区时，采用的是等长的，不相交的分区。
  作者的理由也很简单：因为更复杂的分区，没有带来更好的效果。同时我们也假设数据在各维度之间是独立的。

• 那为什么要对维度分区呢？放在一起排希尔伯特曲线不行么？
  关键在于希尔伯特曲线也是一种近似，它不一定能完美刻画出对象在欧式空间中的真实距离关系。但是通过对不同维度分别做模拟，我们认为，只要至少在一个分区里有邻近关系，就可以作为一个candidate等待后续检验。【编者：这种思想类似于LSH方法中的多个grid，用多次独立校验降低近似方法的失误率】

  
  
  image.png

3.2 RDB-trees

希尔伯特曲线建好了，下面该建B树了。考虑B树的叶子节点内容：

• 如果是数据偏移量，那查询时就要引起太多次随机IO；
• 如果存数据点本身，那么一个叶子节点也存不了几个数据点；
• 最终作者选择了存储数据到reference points的距离，假设有m个锚点，那就存m个距离。

image.png

3.3 Reference Object Selection

由于距离近似的方案的特征是：真实距离越近，近似效果越好。
因此考虑锚点中要至少有一个离query比较近，那么锚点就要在整个空间中分布的较为稀疏。

作者选用了一个锚点选择算法称为SSS(sparse spatial selection稀疏空间选取)，主要步骤如下：

1. 首先估量图的直径，即数据集中任意两点最远距离，方法如下：
   1. 随机选择一个点，找到其最远的邻居，记录最远距离；
   2. 访问这个最远的邻居，在以其为中心，找它最远的邻居，维护最远距离；
   3. 重复1.2.直到收敛或到达给定迭代轮数；
2. 随机选第一个点作为锚点；
3. 每一轮在整个数据集中扫描，直到找到一个点，它和当前锚点集中的所有点的距离不小于f（取0.3）倍的图直径。
4. 重复3.，直到找够所有的点。

3.4 Tuning of Parameters

一个关键的参数是分区个数，分区太多，查询慢；分区太少，精度低。

3.5 Analysis

3.5.1 Time and Space Complexities

构建索引的时间复杂度作者默认读取数据集在整个内存中，这在大数据集下不大合理，因此略过。
索引大小的部分，这里放上总的空间复杂度，注意到数据集大小也就是O(nd)，所以在非物化的情况下，索引比数据还要大数倍。

4. QUERYING

检索分三步，下面分三个小节来讲。

4.1 Retrieving Candidates from RDB-trees

第一步很简单，将query按照刚才构建时的方法，将维度分区，然后得到各分区的希尔伯特键，去分别检索各分区的RDB-tree，将每个RDB-tree target leaf中附近的个数据点都捞出来做candidates.

4.2 Refining Candidates using Approximation

对于每个candidate，都可以利用和锚点的距离，以及query和锚点的距离，做一个和Query距离的下界。（三角不等式）
【编者：度量空间惯用手法】

image.png

下一步，根据托勒密不等式，再次估算距离：

image.png

• 托勒密不等式比三角不等式更紧，但是代价更高。
• 不幸的是，通过实验来看，这个不等式并不能提升多少精确度，因此连作者也不用这个了。
  每个分区的RDB-tree都会产生个candidates，我们将其归并起来。本阶段结束。

4.3 Retrieving k Nearest Neighbors

最后这至多个候选集，逐一去源数据集取数据算真实距离，得到KNN。

4.4 Analysis

4.4.1 Time and Space Complexities

• 内存CPU计算，应该不是限速步，因此编者省略这里的分析。
• 随机磁盘访问次数：访问RDB树需要次IO，最后从候选集选择KNN，需要次IO，总计，实际情况估计是数千次IO这个级别。

5. EXPERIMENTS

C++ 编写 Intel(R) Core(TM) i7-4770 3.4 GHz CPU, 32 GB内存， 2 TB 磁盘，OS： Linux Ubuntu 12.04.
数据集情况

image.png

5.2 Internal Parameter Tuning

参数方面，锚点的个数一般取10，RDB树的个数一般取8，高维取16

image.png

image.png

5.3 Quality Metrics

• index size比HNSW还要大，好在是disk-based的；
• query time不占优势，算是勉强过关；
• RAM消耗当然是较少的，因为是disk-based index；

• 精度方面不如OPQ和HNSW，说明比较一般了。

  
  
  image.png
  
  
  image.png

5.6 Summary

image.png