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

编者的总结

编者的思考

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

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

image.png

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

image.png

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

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

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

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

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

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

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

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

image.png

m个锚点，就有m个下界，取其中的最大值即是最紧的下界。
根据下界距离，将原有的candidate进行排序，取前

\beta

个保留。

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

image.png

托勒密不等式需要2个锚点，因此就有

C_m^2

种选择，取其中最大的即可。从

\beta

个candidates中，再排序选出前

\gamma

个。

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

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

内存CPU计算，应该不是限速步，因此编者省略这里的分析。
随机磁盘访问次数：访问RDB树需要 $O(log_\theta n +(\alpha/\Omega))$ 次IO，最后从候选集选择KNN，需要 $O(\tau\gamma)$ 次IO，总计 $O(\tau(log_\theta n +(\alpha/\Omega) + \gamma))$ ，实际情况估计是数千次IO这个级别。