1. 背景介绍
LSH是用局部敏感的方法解决近似最近邻搜索的问题。在原始的LSH方法中，通过将原始空间嵌入到Hamming空间中，将d维空间转换成d′=Cd维的Hamming空间 (C是指原始空间中点的坐标的最大值)，使用(r,(1+e)r,1−r/d′,1−(1+e)r/d′)-sensetive 哈希函数来解决(r,e)-Neighbor问题。
而后来提出的p-stable LSH算法中，不需要将原始空间嵌入到Hamming空间中，可以直接在欧氏空间下进行局部敏感哈希运算。
p-stable LSH应用在d维Lp-norm下的欧氏空间中，0<p≤2。
p-stable LSH使用的(r,cr,p1,p2)-sensetive哈希中，c=1+e，下面的工作主要是确定在1 (即r) 和 c (即cr) 下的p1与p2。
2. 概念解释
p-稳定分布的概念：
一个分布D如果称为p-稳定分布，则对于任意n个实数v1,v2,…,vn和符合D分布的n个独立同分布随机变量X1,X2,…,Xn，都存在一个p≥0，使得变量∑iviXi和∑i(|vi|p)1/pX (i.e.,||v||pX) 具有相同的分布，此处X是一个符合D分布的随机变量。
p-稳定分布不是具体的分布，而是满足某条件的分布族。
- Cauchy Distribution, pdf为c(x)=1π11+x2, 1-stable.
- Gaussian Distribution, pdf为g(x)=1√2πe−x2/2, 2-stable.
p-stable分布有一个重要的应用，就是可以估计给定向量v在欧氏空间p-norm下长度，记为||v||p。
方法是对于取定的d维向量v，从p-稳定分布中抽取d个随机变量组成d维向量a，计算a与v的点积a⋅v。
根据p-stable的定义，由于a⋅v=∑i(|vi|p)1pX，具有相同的分布，此处X是一个符合D分布的随机变量。选取若干个向量a，计算多个a⋅v的值，称为向量v的概略 (sketch) ，利用v的“sketch”可以用来估算||v||p的值。
3. 局部敏感哈希函数
在p-stable LSH中，a与v的点积a⋅v不用来估计||v||p的值，而是用来生成哈希函数族，且该哈希函数族是局部敏感的 (即空间中距离较近的点映射后发生冲突的概率高，空间中距离较远的点映射后发生冲突的概率低) 。
大体方法是将一条直线分成等长且长度为r的若干段，给映射到同一段的点赋予相同的hash值，映射到不同段的点赋予不同的hash值。(a⋅v1−a⋅v2)是映射后的距离，而其值与||v1−v2||pX同分布，原始距离||v1−v2||p较小时，映射后的距离也小，因此使用点积来生成哈希函数族可以保持局部敏感性。
哈希函数族的形式为：
ha,b=⌊a⋅v+br⌋其中b是(0,r)里的随机数，r为直线上分段的段长。哈希族中的函数根据a和b的不同建立函数索引。
从哈希函数族中随机选取一个哈希函数，现在估计两个向量v1和v2在该哈希函数下映射后发生冲突的概率。
定义符合p-stable分布的随机变量绝对值的概率密度函数为fp(t)。设c=||v1−v2||p，则a⋅v1−a⋅v2与cX同分布，X为p-stable分布下的随机变量。给出概率的计算公式如下，之后会有详细分析。
p(c)=Pra,b(ha,b(v1)=ha,b(v2))=∫r01cfp(tc)(1−tr)dt其中|a⋅v1−a⋅v2|=||v1−v2||p|X|=c|X|，X为p-stable分布下的随机变量，|X|的概率密度函数为fp(t)。
若要向量v1和v2映射后发生冲突，需要满足如下条件：v1和v2通过与a进行点积运算分别映射到一段长度为r线段后，再通过加b运算，能使映射后的点在同一条线段上。
4. 结语
p-stable LSH通过稳定分布和点积的概念，实现了LSH算法在欧氏空间下的直接应用，而不需要嵌入Hamming空间。p-stable LSH中，度量是欧氏空间下的Lp准则，即向量v1与v2的距离定义为||v1−v2||p，然后通过设定的哈希函数将原始点映射到直线的等长线段上，每条线段便相当于一个哈希桶，与LSH方法类似，距离较近的点映射到同一哈希桶 (线段) 中的概率大，距离较远的点映射到同一哈希桶中的概率小，正好符合局部敏感的定义。