如果我们的目标是计算每一对文档对之间的相似度，那么我们就没有更好的办法了，或者可以用并行的方法减少运行的时间规模；但是如果我们的目的仅仅是找到的最相似的文档对或者相似度在某种程度之上的文档对，这时候我们就可以采用LSH技术（locality-sensitive hashing or near-neighbor search）。
简介
在很多应用领域中，我们面对和需要处理的数据往往是海量并且具有很高的维度，怎样快速地从海量的高维数据集合中找到与某个数据最相似（距离最近）的一个数据或多个数据成为了一个难点和问题。如果是低维的小数据集，我们通过线性查找（Linear Search）就可以容易解决，但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常耗时，因此，为了解决该问题，我们需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest Neighbor,AN），例如K-d tree；或近似最近邻查找（Approximate Nearest Neighbor, ANN），例如K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而LSH(局部哈希敏感)是ANN中的一类方法。
原理：
这些hash function需要满足以下两个条件：
- 如果$d(x,y) ≤ d1$， 则$h(x) = h(y)$的概率至少为$p1$；
- 如果$d(x,y) ≥ d2$， 则$h(x) = h(y)$的概率至多为$p2$；
其中$d(x,y)$表示x和y之间的距离，$d1 < d2$， $h(x)$和$h(y)$分别表示对x和y进行hash变换。
满足以上两个条件的hash functions称为$(d1,d2,p1,p2)-sensitive$。而通过一个或多个$(d1,d2,p1,p2)-sensitive$的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing。
引入问题
一般来说，我们这样应用LSH技术：将所有的items（要比较的东西）进行多次的hash，从而能够将可能相似的文档hash到同一个bucket中；然后我们会只考虑那些hash到同一个bucket中的items，认为他们组成的item对才有可能是我们要找的item对。 这其中就会产生两个概念，一个是 false positives: 就是指那些本来不相似的item对却被hash到一个bucket中；另一个是false negatives： 指那些本来相似的items对却没有被hash到同一个bucket中。
文献： Practical and Optimal LSH for Angular Distance