背景
在最近邻的搜索算法中，数据的维度不同，适用的算法也不同，一般来说，准确的暴力计算只适用于在维度较低的时候，在高维大规模情况下计算成本过高，耗时，一般采用近似搜索算法。
1~2维： Voronoi diagrams
10维： kd trees，metric trees, ball-trees，spill trees
高维大规模最近邻搜索： 近似搜索算法，LSH，矢量量化方法等
本文主要介绍近似搜索算法中常见的 局部敏感哈希
局部敏感哈希（LSH)
局部敏感是哈希函数的一种性质：如果相近的样本点对经过哈希后比相远的样本点对更容易发生碰撞。准确地定义如下：
d(x,y)表示x和y之间的距离， h(x)和h(y)分别表示对x和y进行hash变换，d1<d2
1）如果d(x,y) ≤ d1， 则h(x) = h(y)的概率至少为p1；
2）如果d(x,y) ≥ d2， 则h(x) = h(y)的概率至多为p2；
满足以上两个条件的hash functions称为(d1,d2,p1,p2)-sensitive。
通过一个或多个(d1,d2,p1,p2)-sensitive的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing。
LSH的工作原理是通过hash函数首先将所有的样本点映射到不同的桶中，在查询样本的最近邻时，将其做相同的变换，查询样本的最近邻很大概率会在查询样本落入相同的桶中，只需要在桶中进行搜索即可，不用在所有数据集中遍历，进而加速了查找。
LSH可以不只设置一个hash表，也可以不只在一个桶中搜索，LSH通常包含了三个主要参数：
- K， 表示一个Hash表被哈希函数划分得到的空间数，即一个hash函数得到的桶的数目；
- L， hash表的数目，一个hash表可以分为K个空间；
- T， 查找桶的个数，所有的hash表中，一共可以在多少个桶中进行查找。
这三个设置参数可以按照如下顺序进行：首先，根据可使用的内存大小选取L，然后在K和T之间做出折中：哈希函数数目K越大，每个桶中的元素就越少，近邻哈希桶的数目的数目T也应该设置得比较大，反之K越小，L也可以相应的减小。获取K和L最优值的方式可以按照如下方式进行：对于每个固定的K，如果在查询样本集上获得了我们想要的精度，则此时T的值即为合理的值。在对T进行调参的时候，我们不需要重新构建哈希表，甚至我们还可以采用二分搜索的方式来加快T参数的选取过程。
使用LSH对海量数据进行最近邻查找的过程如下：
- 离线建立索引
（1）选取满足(d1,d2,p1,p2)-sensitive的LSH hash functions；
（2）根据对查找结果的准确率（即相邻的数据被查找到的概率）确定hash table的个数L，每个table内的hash functions的个数K，以及跟LSH hash function自身有关的参数；
（3）将所有数据经过LSH hash function哈希到相应的桶内，构成了一个或多个hash table；
- 在线查找
（1）将查询数据经过LSH hash function哈希得到相应的桶号；
（2）将桶号中对应的数据取出；（为了保证查找速度，通常只需要取出前2L个数据即可）；
（3）计算查询数据与这2L个数据之间的相似度或距离，返回最近邻的数据；
不同距离度量方式有一些常用的hash函数，具体可以参见：https://blog.csdn.net/icvpr/article/details/12342159
参考文章：
http://www.cs.cmu.edu/~agray/approxnn.pdf
https://yongyuan.name/blog/ann-search.html
https://blog.csdn.net/icvpr/article/details/12342159
