标题：优化KD树用于快速图描述符匹配

编者的总结：

1. 第一个贡献在于使用旋转矩阵构建多棵（近似）独立的树；
2. 第二个贡献在于使用随机的分割维度构建多棵树；
3. 第三个贡献在于使用PCA预处理。
4. 思路上的核心贡献在于重整搜索顺序，构造更多搜索可能，设计搜索不同节点之间的独立性。

编者的思考

1. 本文的方法应该适用于很多动态的树型索引结构，通过一定的随机化和数据预处理，制造多棵树，形成独立性以提升质量。
2. 这种建立多棵树寻求多次独立搜索以提高近似质量的思路，和LSH有异曲同工之处。
3. 评价指标比较单一。

Abstract

本文对于KD树的提升，主要在于在同一个数据集上创建多个KD树（森林），在这个森林范围上同时进行优先级搜索。
另外一个贡献，在于对SIFT数据集的结构，或者任意数据集的结构进行利用。用PCA将主要维度对齐。

1. Introduction

1.1 Outline of KD-tree search.

首先说到kd-tree的搜索顺序问题。由于kd-tree的叶子节点一般是1（也有可能是几个），所以搜一个节点一般是不行的，要额外搜一些其它节点，决定这个搜索顺序有两种方式：

• 一种传统的办法就是沿着父亲路径往上爬，称为backtracking；

• 另一种方法就是设置优先级队列，按照和query的距离决定去搜索哪些节点，这个距离有一个上界，就是不能超过当前BSF，否则没有意义，如下图所示，先搜了点1，则范围是大圆内的，然后搜到了3，变成了小圆内的；小圆内的所有格子都搜完了，则查询终止。

  
  image.png

• 为了避免这个查询时间过长，通常设置一个最多搜索的叶子节点数，显然，搜的越多，搜到真实1NN的概率也就越大，但是不同搜索方式的概率增长速度是不一致的。【图中没搜到1NN的概率】

  
  image.png

• 然而PQ搜索顺序仍然不是最佳的，因为搜的节点越多的时候，搜索的回报反而减少了。也就是说要想和搜第一个或者前面的节点达到一样的找到1NN的概率，就需要搜更多节点，付出更多的代价。
  事实上，我们希望每次搜索都是一次独立重复实验。比如搜一次没搜到的概率是，那么搜n次仍然没搜到的概率就期望是，取个负对数，则，y与n应当是线性的关系（如下图），但目前的pq搜索顺序还远远达不到线性。
  

  image.png

• 本文的Motivation就是改善搜索顺序，提升每次搜索的独立性，具体策略是：

  1. 创建m棵不同的kd-tree使得在不同树上的搜索很大程度上是独立的；
  2. 给定搜索限制为n个节点，本文让m棵kd-tree，每棵搜n/m个节点；
  3. 使用PCA旋转数据进行搜索。

作者提到，无论是构建多棵树，还是旋转kd-tree，都会显著提升搜索性能，组合使用将会锦上添花。

1.2 Previous work

kd-tree在高维情况下效率降低的主要原因就是backtrack的过程耗时太长，如果去限制搜索节点个数，实际上就是近似，本文就是来提升这个近似质量。

2. Independent multiple searches

• 首先一个论点是搜索的节点越多，搜索的精度越高。
• 但是由于按目前的优先级队列顺序进行搜索，各节点间并非是独立的，搜的节点越多，搜索的质量密度反而下降了。
• 另一方面，kd-tree的构建参数不同，搜索顺序，搜索质量可能都不一样。
• 这两点共同促使产生多颗kd-tree的思想，以增强搜索的独立性。

2.1 Rotating the tree

首先将数据集进行旋转，利用一个旋转矩阵R，利用旋转后的数据集建kd-tree，然后删掉处理过的数据集，保留原数据集和kd-tree。多颗kd-tree就意味着多个不同的旋转矩阵R。
查询时候也用Rq对kd-tree进行查询，坐标轴旋转前后，对距离是不产生影响的。

2.2 Are rotated trees independent?

直接通过查询精确程度来判定，NKD，也就是旋转过后的森林（10棵树），更逼近线性，说明独立性有了很大提升。

image.png

2.3 A saving using Householder matrices.

正常来说通过旋转矩阵处理一个向量，复杂度；考虑到旋转只有两个目的：1. 换一组正交基；2. 保持模长为1 。那么实际上任何正交变换都可以完成这个目的。
为了节省时间，就选择Householder变换矩阵，这个的时间复杂度是。

2.4 Searching multiple trees

在m棵树之间，共享一个优先级队列，将叶子节点按照与query的距离进行排序。首先在m棵树上都找到target leaf node，计算距离即BSF，节点与query距离超过BSF的自然不需要入队了。

2.5 Space requirements.

用数组来实现树索引结构，在索引中每个向量仅需6B存储在叶子节点中。整个森林被称为NKD-tree。

2.6 A different randomisation: RKD-tree.

考虑到NKD-tree做旋转的目的就是在同一个数据集上做出不同的kd-tree结构，那么不用旋转，其他方式也可以。比如在分割维度选择上，其实很多维度方差都很大，就可以在这些方差比较大的维度上随机选择，在顶层不同选择，就可以造出结构各异的kd-trees。这种方法不仅省去了预处理的时间，而且效果上甚至好于NKD-tree。

3. Modelling KD-trees.

这个Section主要是讲如何在数学上去模拟KD-tree的表现。核心的手段就是在低维空间中去模拟其行为。
作者举了个例子，比如128维的SIFT向量，1M的数据集，kd-tree也就是20层，那么至多也就比较了20个维度。作为找到的向量x，x和q可能至多也就在那么20个维度上是相近的，在其他维度则不一定。

3.1 The virtual projection.

根据上面的例子，大部分的维度是和索引无关的，那么我们可以假设首先将数据集映射到那么n个相关的维度上，然后进行构建索引、查询，因为映射不是真实发生的，因此称为虚拟映射。

这样在虚拟映射下，我们认为数据集已经被降维了，query q也被同样降维了。查询时按照映射过的q进行排序，访问。

3.2 Probability analysis

• 目前的核心问题在于：虚拟映射过后，1NN和query q还是否相近？
  很遗憾，答案是不一定。观察图5左上，虽然1NN还是第一位排序的概率是最大的，但图中仍然显示有长尾，意味着仍然有很多可能，1NN被排到了很后面的位置，造成搜索失败。
  并且也解释了为什么用kd-tree进行精确搜索时要搜很长一个list。

作者之后用几个实验主要来表名搜得越多，回报越少。用几个独立的kd-tree之后，逐渐改善了这一现象。【编者：这几个实验和解释有一些蹊跷，日后有空会对其做出解释】

image.png

4. Principal Component Trees

通过第三节的虚拟映射分析，我们可以知道，kd-tree对于高维数据的失败，一个很重要的原因就是在于kd-tree实际上存在某种虚拟映射，虚拟映射后，本来和query不相近的点，被映射到了和1NN相近的位置。因此调整这种虚拟映射的方向，把数据映射到主要分割维度上，就很重要。
很自然的想法就是通过PCA预处理数据，然后挑选维度。当使用多棵kd-tree时，旋转时也要务必保留前几个最重要的基不要旋转。

这种算法称为PKD-tree。

5. Experimental results

500K个SIFT向量，20K个query加上高斯噪声，128维，数据正规化过。
这张图就是所有的实验结果了。

• 首先是NKD和RKD效果是差不多的；
• 用了PCA之后，即使单棵树也有一定提升；
• 如果不对旋转维度加以限制，多棵树的提升将会受到限制；

• 限制30维之后，多棵树的提升更明显一些了。

  
  image.png