高维相似性搜索在基于内容的检索中日益重要，具有丰富的音频、图形和传感器数据等特征。KNN和ANN。
理想的类似搜索索引策略应满足以下特点。
准确性：返回的结果要和BF返回结果近似，用查全率表示。
时空：如果是查询时间o(1)或者o(logn)，空间不能超过源数据。对于大数据，我不会定量分析主存的容忍范围。
高维度：在高维度下表现良好。
用于KNN的树结构有R、SR、KD、覆盖树木和导航网这些方法返回的结果准确，但在高维空间下表现不佳，时间比较BF慢，就是这样，提出的LSH，LSH主要思想是以更大的概率将原始空间中相距较近的点映射到同一个桶中，而较远的点则映射到不同的桶中。在了提高准确性，需要多个哈希表，哈希表的数量与数据量成正比，大数据下的空间效率难以忍受。 1.2 算法背景
传统的LSH为了保证良好的搜索效率，需要大量的哈希表。多探针哈希可以智能地探测可能包含结果的多桶，该方法基于熵LSH灵感(主要是减少传统)LSH根据评价，时空效率有所提高。 二.LSH简介
位置敏感哈希(Locality Sensitive Hashing,LSH)它是最流行的近邻搜索算法之一，具有坚实的理论基础，在高维数据空间中表现良好。由于网络上相关知识的介绍相对单一，现在LSH介绍和总结相关算法和技术，希望能为感兴趣的朋友提供便利，也希望感兴趣的同事多交流，多纠正。 2.1 LSH原理
最近邻问题（nearest neighbor problem）可以定义如下：给定n个对象的集合并建立一个数据结构。当给定任何查询对象时，数据结构返回最相似的查询对象。LSH基本思想是利用多个哈希函数将高维空间中的向量映射到低维空间，用低维空间的编码表示高维向量。根据其分布和自身特点，通过对向量对象进行多次哈希映射，高维向量落入不同哈希表的不同桶中。理想情况下，可以认为接近高维空间的向量对象近的向量对象很有可能最终落入同一桶，而距离较远的对象很有可能落入不同的桶。因此，在查询过程中，通过对查询向量进行同样的多次哈希操作，综合多个哈希表中的查询操作，得到最终结果。
利用哈希函数过滤整个数据集，获得可能满足查询条件的点，避免查询点与数据集中的所有点之间的距离计算，提高查询效率。 2.2 LSH函数族
公式不好写。 2.2 LSH构建和搜索索引
1.索引构建
在创建LSH索引时，选择的哈希函数是kLSH函数的串联函数相对增加了接近点冲突的概率p1远距离点冲突的概率p2之间的差值,但这同时也使这两个值一起减小了,于是需要同时使用L张哈希表来加大p1同时减小p2。通过这样的构造过程,在查询时,与查询点q距离近的点就有很大的概率被取出作为候选近似最近邻点并进行最后的距离计算,而与查询点q距离远的点被当作候选近似最近邻点的概率则很小,从而能够在很短的时间内完成查询。
2.查找
在L张表中找到相关桶，取并集。 三.基于p-stable的LSH的介绍
对应海明距离LSH称为位采样算法（bit sampling），该算法是哈希值的海明距离，但一般距离由欧洲距离测量，将欧洲距离映射到海明空间，然后比较海明距离更麻烦。因此，研究人员提出了基于p-具有稳定分布位置的敏感哈希算法可以直接处理欧洲距离。 3.1 p-stable分布
定义:实数集R上的分布D，如果存在P>=0，任何n个实数v1,…,vn满足D分布和n的变量X1,…,Xn，随机变量ΣiviXi和(Σi|vi|p)1/pX有相同的分布，其中X是服从D分布的随机变量，称为D 稳定分布的p。 对任何p∈稳定分布： p=1是柯西分布，概率密度函数为c(x)=1/[π(1 x2)]； p=2时为高斯分布，概率密度函数为g(x)=1/(2π)1/2*e-x^2/2。 利用p-stable分布能有效地接近高维特征向量，并在保证测量距离的同时降低高维特征向量的维度。关键思想是产生d维的随机向量a，随机向量a中的每一维都是随机和独立的p-stable产生分布。对于的特征向量v，如定义，随机变量a·v具有和(Σi|vi|p)1/pX因此，可以使用相同的分布a·v估计表示向量v||v||p 。
作者认为介绍p-stable原因是保距性质(因为LSH与构造和构造相当于降维)。 3.2 基于p-stable哈希函数族
p-Stable分布的LSH利用p-Stable使用它给每个特征向量v一个哈希值。哈希函数是局部敏感的，所以如果v1和v2.如果距离很近，它们的哈希值会相同，被哈希放入同一桶的概率会很大。 根据p-Stable分布，两个向量v1和v2的映射距离a·v1-a·v2和||v1-v2||pX 分布是一样的。 a·v将特征向量v映射到实数集R，如果实轴以宽度w等分，并标记每一段，a·v当它落到那个范围时，将该范围标记作为哈希值赋予它。该方法构建的哈希函数对两个向量之间的距离有局部保护作用。
ha,b(v) = floor(a*v b/w)。
b在[0,w]内，其中av是点乘（a是行向量)，但是具体实现的时候，可以结合构造。av作为矩阵乘法，a行数和构建LSH数目k，是一锅端。 3.3 碰撞概率检测
随机选择一个哈希函数ha,b(v)，则特征向量v1和v如何计算掉在同一桶里的概率？ 首先定义c=||v1-v2||p，fp(t)为p-Stable分布向量v1和v2映射到随机向量a的距离是|a·v1-a·v2|<w，即|(v1-v2)·a|<w，根据p-Stable分布特性，||v1-v2||pX=|cX|<w，随机变量X满足p-Stable分布。 碰撞概率可以获得p?:
根据该公式，随着距离c的增加，两个特征向量的冲突碰撞概率可以降低。 3.4 相似性搜索
哈希函数哈希后，g(v)=(h1(v),…,hk(v))，但将(h1(v),…,hk(v))直接存入哈希表，即占用内存，又不便于查找，为解决此问题，现定义另外两个哈希函数：
因为每个哈希桶（Hash Buckets）gi被映射成Zk，函数h一是普通哈希策略的哈希函数，函数h用于确定链表中的哈希桶。 (1)将哈希桶存储在链表中gi(v)=(x1,…,xk)当时，其实只存在h2(x1,…,xk)结构的指纹不存储向量(x1,…,xk)，所以哈希桶gi(v)=(x1,…,xk)在链表中的相关信息仅有标识(identifier)指纹h2(x1,…,xk)桶中的原始数据点。 (2)使用哈希函数h而不是存储gi(v)=(x1,…,xk)价值有两个原因：一是使用h2(x1,…,xk)结构指纹可以大大降低哈希桶的存储空间；其次，使用指纹值可以更快地检索哈希表中的哈希桶。选择一个足够大的值，以确保两个不同的哈希桶在链表中有不同的概率h2指纹值。
注意 例如，你有1万个数据，其中许多很容易被哈希联系在一起 ，假设10个被哈希期望在一起 ，然后你的表长会1000，这是假设，看实际情况，比如你的测试 发现不同的哈希值有n个 表长控制在1.3n正常的哈希表可以减少冲突 空间利用率在60-70%之间，事实上，对于1万个数据点 假如你的哈希表长为1万，肯定可以装下。事实上，这个参数可以事后确定。 3.5 不足与缺陷
LSH方法有两个缺点：一是基于概率模型生成索引编码的典型结果不稳定。虽然编码位数增加，但查询准确性确实很慢；其次，需要大量的存储空间，不适合大规模数据的索引。E2LSH该方法的目标是确保查询结果的准确性和完整性，而不注意索引结构所需的存储空间。E2LSH使用多个索引空间和多个哈希表查询，生成的索引文件的大小是原始数据大小的几十倍甚至几百倍。 四.基于熵的LSH简介 4.1 介绍
Entopy-based LSH结构索引和基础LSH策略相似，但采用了不同的查询过程。该方法随机生成几个接近查询数据的扰动查询数据(perturbing query objects)，将这些数据和待查询数据一同进行哈希，将所有的结果汇总得到候选集。 Entopy-based LSH采样哈希桶的方法是每次将与查询数据Q的距离为Rp的随机数据p哈希，得到p相应的哈希桶；多次采样，以确保所有可能的桶都被检测到(probe)到。 4.2 不足
首先，该方法的采样过程效率不足，扰动数据的生成和哈希值的计算速度缓慢，不可避免地会得到重复的哈希桶。这样，高概率映射桶就会多次计算，这是浪费。 另一个缺点是，采样过程需要对近邻距离Rp对数据相互之间的情况有一定的了解是困难的。Rp如果太小，扰动查询数据可能无法产生足够的候选集；Rp如果太大，需要更多的扰动查询数据来保证更好的查询质量。 五.Multi-Probe LSH算法概述
Multi-Probe LSH该方法的关键是使用仔细推导的探测序列(carefully derived probing sequence)，多个哈希桶类似于查询数据。 根据LSH我们可以知道，如果类似于查询数据q的数据没有映射到与q相同的桶中，它很可能会映射到周围的桶中（即两个桶的哈希值只有一点不同），因此该方法的目标是定位这些相邻的桶，以增加找到相邻数据的机会。
首先，我们定义哈希微扰向量(hash perturbation vector)Δ=(δ1,...,δM)，给定一个查询据q，基本LSH方法得到的哈希桶是g(q)=(h1(q),...,hM(q))，我们定义微扰Δ，我们可以探测到哈希桶g(q)+Δ。
回想LSH函数
如果我们选择合理的W，那么相似的数据应该映射到相同或者临近的哈希值上（较大的W使得这个值相差最多一个单位），因此，我们关注微扰向量Δ在δi={-1，0，1}
微扰向量直接作用于查询数据的哈希值上，避免了Entopy-based LSH方法中扰动数据计算和哈希值计算的天花板问题(overhead)。该方法设计的微扰向量序列(a sequence of pertubation vectors)中，每个向量都映射成一个唯一的哈希值集合，这样就不会重复探测一个哈希桶了。
参考文献http://blog.csdn.net/jasonding1354/article/details/44080537
扰动序列的产生http://jasonding1354.github.io/2015/03/05/Similarity%20Search/%E3%80%90Similarity-Search%E3%80%91Multi-Probe-LSH%E7%AE%97%E6%B3%95%E6%B7%B1%E5%85%A5/