<p><strong><span style="color:#4d6df3">一、原始LSH</span></strong><br> </p>
<div>
<div>
<div>
1、概述
</div>
<div>
LSH主要用来解决高维空间中点的近似最近邻搜索问题，即Approximate Nearest Neighbor。LSH将原始空间中的点嵌入到Hamming空间中，即原始空间中点的表达形式转换成Hamming空间中点的表达形式，原始空间中的距离度量转换成Hamming空间中的距离度量。这样，原始空间的e-NNS(定义见下文)问题就转变成Hamming空间中的e-KNN问题了。LSH方法提高了空间使用率，其搜索时间与维度线性相关的，与空间规模次指数相关，大大缩短了搜索时间。适用于解决不需要精确解，只需要得到近似解的问题。
</div>
<div>
<br>
</div>
<div>
2、相关概念
</div>
<div>
（1）哈希桶（Hash Bucket）:哈希表中同一个位置可能存有多个元素，以应对哈希冲突问题。这样，哈希表中的每个位置表示一个哈希桶。
</div>
<div>
（2）e-NNS问题：对于一个查询子q，返回空间中的一个点p，使得d(q,p) <= (1+e)d(q,P)，d(q,p)表示查询子与空间中点p的距离，d(q,P)表示查询子距空间点集P中最近点之间的距离。
</div>
<div>
（3）局部敏感：称一个函数族H={h:S->U}是(r1,r2,p1,p2)局部敏感的，如果满足下面两个条件（D为空间距离度量,Pr表示概率）：
</div>
<div>
1）若空间中两点p和q之间的距离D(p,q)<r1，则Pr(h(p)=h(q))>p1
</div>
<div>
2）若空间中两点p和q之间的距离D(p,q)>r2，则Pr(h(p)=h(q))<p2
</div>
<div>
条件在r1 < r2，p1 > p2的条件下有意义。
</div>
<div>
通俗来讲，就是距离较近的点映射到同一个位置的概率大，距离较远的点映射到同一个位置的概率小。这对下面将点集映射得到候选结果集的操作很重要，能保证得到的候选结果集是可用的。
</div>
<div>
<br>
</div>
<div>
3、算法思想
</div>
<div>
定义一系列Hash函数h1,h2,…,hn，随机选取其中的k个函数组成函数g(x)，不妨设选的是h1到hk，则g(x)=（h1(x),h2(x),…,hk(x)），像这样选取L个的g函数：g1(x),g2(x),…,gl(x)，每个函数对应一个哈希表。对于原始空间中的每一个点p，通过每个g函数分别映射到L个哈希桶中。这样，每个点都会在L个哈希表的某个哈希桶中出现。查询时，给定了查询子q，利用L个g函数同样对q进行映射，将与q落在同一个哈希桶中的点作为候选结果集，计算q与候选结果集中的点之间的距离，并从中选出1个或K个距离最近的点。
</div>
<div>
简单的讲，就是讲原始的点集按距离分成不同的类，查询与q距离较近的点集时，只需比较和q在同一类中的点集，而不需要比较全部点集。从而节省了搜索时间。
</div>
<div>
<br>
</div>
<div>
4、算法步骤（L1准则下的欧几里得空间嵌入Hamming空间中）
</div>
<div>
因为许多符号不好打，并且内容较多，如果有需要详细步骤的，可以发邮件。gynvsnash@gmail.com
</div>
<div>
或参考
<a href="http://wenku.baidu.com/view/c616e7c008a1284ac85043cd.html" rel="noopener noreferrer" target="_blank">http://wenku.baidu.com/view/c616e7c008a1284ac85043cd.html</a>
</div>
<div>
里面包括算法步骤和算法分析。
</div>
<div>
<br>
</div>
<div>
<br>
</div>
<div>
二、
<strong><span style="color:#4d6df3">p-stable LSH</span></strong>
</div>
<div>
LSH是用局部敏感的方法解决近似最近邻搜索的问题。在原始的LSH方法中，通过将原始空间嵌入到Hamming空间中，将d维空间转换成d＇=Cd维的Hamming空间（C是指原始空间中点的坐标的最大值，具体情况参见上一部分中的第4节-算法步骤），使用(r,(1+e)r,1-r/d＇,1-(1+e)r/d＇)-敏感哈希函数来解决(r,e)-Neighbor问题。而后来提出的p-stable LSH算法中，不需要将原始空间嵌入到Hamming空间中，可以直接在欧几里得空间下进行局部敏感哈希运算。
</div>
<div>
1、背景介绍
</div>
<div>
p-stable LSH应用在d维lp-norm下的欧几里得空间中，0<p<=2。p-stable LSH是LSH的进化版本，要解决的问题相同，而使用的方法和应用环境不同。因此，下面重点介绍p-stable LSH的应用环境，对于LSH的细节参见第一部分。
</div>
<div>
p-stable LSH使用的(R,cR,p1,p2)-敏感哈希中，c=1+e，并且不失一般性，设R=1。下面的工作主要是确定在1（即R）和c（即cR）下的p1与p2。
</div>
<div>
2、概念解释
</div>
<div>
p-stable LSH之所以会叫这个名字， |
|
转播
