前言
Locality Sensitive Hash 的主要功能是在海量高维向量中寻找一个向量的近似最临近点，常用于搜索引擎网页去重，相似图像检索，音乐检索等。
本文主要参考资料是:
[1] Slaney, M., and M. Casey. “Locality-Sensitive Hashing for Finding Nearest Neighbors.” IEEE Signal Processing Magazine 2008:128 - 131.
[2] Slaney, M., Y. Lifshits, and J. He. “Optimal Parameters for Locality-Sensitive Hashing.” Proceedings of the IEEE 100.9(2012):2604 - 2623.
参考项目
[1] https://github.com/kayzh/LSHash
[2] https://github.com/RSIA-LIESMARS-WHU/LSHBOX
基本思想
这里有一个不错的隐喻：假设有一个球面，如果球面上的A点和B点是邻近的，那么将球面投影到某个二维平面上，无论以哪个方向投影，A点和B点始终是邻近的;
另一方面，如果球面上的A点和B点不是邻近的，那么以某些特定的方向投影时，A点和B点可能是邻近的，而以大多数其他方向上投影时，A点和B点则不会邻近。
所以我们应该如何定义邻近的概念呢，假设$p$和$q$是$R^d$空间中的两个点,
$$ ||p-q|| \leq R_1 $$
随机投影 RANDOM PROJECTION
$$ h^{x,b}(\vec{v})=\biggl\lfloor\frac{\vec{x} \cdot \vec{v} + b }{w}\biggr\rfloor $$
其中
$\vec{v}$ 是待查询的向量
$\vec{x}$ 是一个随机的方向，其中每一维遵循高斯分布，比如 $N(0,1)$
$w$ hash bin width 哈希桶宽度
$b$ random variable 实际中可为0
补充定义
如果$p$与$q$邻近，那么它们有高于$P_1$的概率落入同一个哈希桶。
$$ P_H[h(p)=h(q)] \geq P_1 \qquad \qquad \qquad for \quad ||p-q|| \leq R_1 $$
如果$p$与$q$不邻近，那么它们有小于$P_2$的概率落入同一个哈希桶。
$$ P_H[h(p)=h(q)] \leq P_2 \qquad \qquad \qquad for \quad ||p-q|| \geq R_2 = cR_1 $$
这样投影有k次，k的经验取值为7-15;以k次随机投影为一组，要进行L组计算，一般L的取值会与以下公式相关。
$$ L= \frac{[ \; log \, \delta \; ]}{log(1-P^k_1)} $$
$\delta$ 为 LSH 未能成功发现真最邻近点的最大概率。
LSHash 中的实现
LSHash 中进一步简化了上述公式。 原本是按 w 划分 hash bin。
在 LSHash 中 简化为 大于0 和 小于0的情况， 分别是 1 和 0 。
感觉可以这样解释，存在一组法向量随机的超平面，相邻近的点更倾向落在这一组超平面的同一侧，而不相邻近的点则无法一直保持在超平面的同一侧。
数据结构则是使用 dict { key: value} 并且 value 是一个 list 。
