上一節(jié)云头，我們分析了LSH算法的通用框架皮假，主要是建立索引結(jié)構(gòu)和查詢近似最近鄰。這一小節(jié)衩椒，我們從p穩(wěn)定分布LSH（p-Stable LSH）入手蚌父，逐漸深入學(xué)習(xí)LSH的精髓，進(jìn)而靈活應(yīng)用到解決大規(guī)模數(shù)據(jù)的檢索問題上毛萌。
對應(yīng)海明距離的LSH稱為位采樣算法（bit sampling）苟弛，該算法是比較得到的哈希值的海明距離，但是一般距離都是用歐式距離進(jìn)行度量的阁将，將歐式距離映射到海明空間再比較其的海明距離比較麻煩膏秫。于是，研究者提出了基于p-穩(wěn)定分布的位置敏感哈希算法做盅，可以直接處理歐式距離缤削，并解決(R,c)-近鄰問題。
p-Stable分布
定義：對于一個實數(shù)集R上的分布D吹榴，如果存在P>=0亭敢，對任何n個實數(shù)v1,…,vn和n個滿足D分布的變量X1,…,Xn，隨機變量ΣiviXi和(Σi|vi|p)1/pX有相同的分布图筹，其中X是服從D分布的一個隨機變量帅刀，則稱D為 一個p穩(wěn)定分布。
對任何p∈(0,2]存在穩(wěn)定分布：
p=1是柯西分布远剩，概率密度函數(shù)為c(x)=1/[π(1+x2)]扣溺；
p=2時是高斯分布，概率密度函數(shù)為g(x)=1/(2π)1/2*e-x^2/2瓜晤。
利用p-stable分布可以有效的近似高維特征向量锥余，并在保證度量距離的同時，對高維特征向量進(jìn)行降維痢掠，其關(guān)鍵思想是驱犹，產(chǎn)生一個d維的隨機向量a嘲恍，隨機向量a中的每一維隨機的、獨立的從p-stable分布中產(chǎn)生着绷。對于一個d維的特征向量v，如定義锌云，隨機變量a·v具有和(Σi|vi|p)1/pX一樣的分布荠医，因此可以用a·v表示向量v來估算||v||p 。
p-Stable分布LSH中的哈希函數(shù)
p-Stable分布的LSH利用p-Stable的思想桑涎，使用它對每一個特征向量v賦予一個哈希值彬向。該哈希函數(shù)是局部敏感的，因此如果v1和v2距離很近攻冷，它們的哈希值將相同娃胆，并被哈希到同一個桶中的概率會很大。
根據(jù)p-Stable分布等曼，兩個向量v1和v2的映射距離a·v1-a·v2和||v1-v2||pX 的分布是一樣的里烦。
a·v將特征向量v映射到實數(shù)集R，如果將實軸以寬度w等分禁谦，并對每一段進(jìn)行標(biāo)號胁黑，則a·v落到那個區(qū)間，就將此區(qū)間標(biāo)號作為哈希值賦給它州泊，這種方法構(gòu)造的哈希函數(shù)對于兩個向量之間的距離具有局部保護(hù)作用丧蘸。
哈希函數(shù)格式定義如下：
ha,b(v):Rd->N，映射一個d維特征向量v到一個整數(shù)集遥皂。哈希函數(shù)中又兩個隨機變量a和b力喷，其中a為一個d維向量，每一維是一個獨立選自滿足p-Stable的隨機變量演训，b為[0,w]范圍內(nèi)的隨機數(shù)弟孟，對于一個固定的a，b样悟，則哈希函數(shù)ha,b(v)為
特征向量碰撞概率
隨機選取一個哈希函數(shù)ha,b(v)披蕉，則特征向量v1和v2落在同一桶中的概率該如何計算呢？
首先定義c=||v1-v2||p乌奇，fp(t)為p-Stable分布的概率密度函數(shù)的絕對值没讲，那么特征向量v1和v2映射到一個隨機向量a上的距離是|a·v1-a·v2|<w，即|(v1-v2)·a|<w礁苗，根據(jù)p-Stable分布的特性,||v1-v2||pX=|cX|<w爬凑，其中隨機變量X滿足p-Stable分布。
可得其碰撞概率p(c):
根據(jù)該式试伙，可以得出兩個特征向量的沖突碰撞概率隨著距離c的增加而減小嘁信。
p-Stable分布LSH的相似性搜索算法
經(jīng)過哈希函數(shù)哈希之后于样，g(v)=(h1(v),...,hk(v))，但將(h1(v),...,hk(v))直接存入哈希表潘靖，即占用內(nèi)存穿剖，又不便于查找，為解決此問題卦溢，現(xiàn)定義另外兩個哈希函數(shù)：
由于每一個哈希桶（Hash Buckets）gi被映射成Zk糊余，函數(shù)h1是普通哈希策略的哈希函數(shù)，函數(shù)h2用來確定鏈表中的哈希桶单寂。
（1）要在一個鏈表中存儲一個哈希桶gi(v)=(x1,...,xk)時贬芥，實際上存的僅僅是h2(x1,...,xk)構(gòu)造的指紋,而不是存儲向量(x1,...,xk)，因此一個哈希桶gi(v)=(x1,...,xk)在鏈表中的相關(guān)信息僅有標(biāo)識(identifier)指紋h2(x1,...,xk)和桶中的原始數(shù)據(jù)點宣决。
（2）利用哈希函數(shù)h2蘸劈，而不是存儲gi(v)=(x1,...,xk)的值有兩個原因：首先，用h2(x1,...,xk)構(gòu)造的指紋可以大大減少哈希桶的存儲空間尊沸；其次威沫，利用指紋值可以更快的檢索哈希表中哈希桶。通過選取一個足夠大的值以很大的概率來保證任意在一個鏈表的兩個不同的哈希桶有不同的h2指紋值洼专。
不足與缺陷
LSH方法存在兩方面的不足：首先是典型的基于概率模型生成索引編碼的結(jié)果并不穩(wěn)定壹甥。雖然編碼位數(shù)增加，但是查詢準(zhǔn)確率的提高確十分緩慢壶熏；其次是需要大量的存儲空間句柠，不適合于大規(guī)模數(shù)據(jù)的索引。E2LSH方法的目標(biāo)是保證查詢結(jié)果的準(zhǔn)確率和查全率棒假，并不關(guān)注索引結(jié)構(gòu)需要的存儲空間的大小溯职。E2LSH使用多個索引空間以及多次哈希表查詢，生成的索引文件的大小是原始數(shù)據(jù)大小的數(shù)十倍甚至數(shù)百倍帽哑。
參考資料：
1谜酒、王旭樂.基于內(nèi)容的圖像檢索系統(tǒng)中高維索引技術(shù)的研究[D].華中科技大學(xué).2008
2、M.Datar,N.Immorlica,P.Indyk,and V.Mirrokni,“Locality-SensitiveHashing Scheme Based on p-Stable Distributions,”Proc.Symp. ComputationalGeometry, 2004.
3妻枕、A.Andoni,“Nearest Neighbor Search:The Old, theNew, and the Impossible”PhD dissertation,MIT,2009.
4僻族、A.Andoni,P.Indyk.E2lsh:Exact Euclidean locality-sensitive hashing.http://web.mit.edu/andoni/www/LSH/.2004.
