引言

上一小節(jié)中，我們初步介紹了Multi-Probe LSH算法的大致思路，為了不顯得博客文章太冗雜，所以將這個(gè)話題分成幾篇文章來(lái)寫是整。
在該小節(jié)文章中，我將具體介紹一下生成微擾向量序列(a sequence of perturbation vectors)的方法及相關(guān)分析民假。

步進(jìn)式探測(cè)(Step-Wise Probing)

n-step微擾向量Δ有n個(gè)非零坐標(biāo)浮入，根據(jù)位置敏感哈希的性質(zhì)，距離查詢q一步遠(yuǎn)(one step away)的哈希桶要比距離q兩步遠(yuǎn)(two step away)所包含的數(shù)據(jù)點(diǎn)更加接近q羊异。
這種想法激發(fā)了步進(jìn)式探測(cè)方法事秀，首先探測(cè)所有相差一步的哈希桶(1-step buckets)，然后再探測(cè)所有兩步的哈希桶(2-step buckets)野舶，以此類推易迹。

對(duì)于LSH索引由L個(gè)哈希表和每個(gè)哈希表中M個(gè)哈希函數(shù)而言，

n-step buckets的總數(shù)是

所有s-step buckets之內(nèi)的桶的總數(shù)是

下圖顯示了K近鄰的桶距離的分布平道。左圖顯示睹欲，單一哈希值差異；右圖顯示一屋，不同于查詢點(diǎn)的哈希值的幾組近鄰哈希值窘疮。
從中可以看出，幾乎所有K近鄰的數(shù)據(jù)都被映射成一個(gè)哈希值或者是存在+1或-1之差冀墨；同時(shí)闸衫，大部分K近鄰數(shù)據(jù)被映射到與查詢數(shù)據(jù)的距離小于2步的哈希桶中。

成功概率的估計(jì)(Success Probability Estimation)

使用步進(jìn)式探測(cè)的方法轧苫，對(duì)于查詢點(diǎn)q來(lái)說(shuō)楚堤，其哈希值的每一個(gè)坐標(biāo)都被等同對(duì)待疫蔓，即對(duì)每一個(gè)坐標(biāo)進(jìn)行微調(diào)(加1或者減1)的機(jī)會(huì)都是等同的含懊。

• 首先，q與一個(gè)方向向量的點(diǎn)積使得q被映射到一條線上衅胀，該線被W分割成幾個(gè)間隔岔乔。與q相鄰的點(diǎn)p很可能被映射在q所在的間隔上或者其相鄰的間隔。
• 實(shí)際上滚躯，p落入q的左右間隔依賴于q與間隔邊界的臨近程度雏门，因此嘿歌，q在每個(gè)間隔中的位置在考慮微擾的構(gòu)造上是潛在的價(jià)值信息。
  The position of q within its slot for each
  of the M hash functions is potentially useful in determining perturbations worth considering.

上圖描述了q的近鄰數(shù)據(jù)落入相鄰間隔的概率茁影。fi(q)=ai·q+bi是哈希函數(shù)hi(q)對(duì)q的映射值宙帝；對(duì)于δ∈{-1,+1}，令xi(δ)為q到間隔為hi(q)+δ的邊界的距離募闲，所以xi(-1)=fi(q)-hi(q)·W步脓、xi(1)=W-xi(-1)；方便起見(jiàn)浩螺，定義xi(0)=0靴患。
對(duì)于一個(gè)固定的點(diǎn)p，fi(p)-fi(q)是一個(gè)均值為0的高斯隨機(jī)變量要出，其方差與p-q的二范數(shù)的平方成比例鸳君。
我們假設(shè)W足夠大，使得近鄰點(diǎn)p有很大的概率映射為hi(q)患蹂、hi(q)+1或颊、hi(q)-1。
所以传于，p落入間隔為hi(q)+δ的概率:

現(xiàn)在饭宾，我們估計(jì)使用微擾向量Δ=(δ1,...,δM)的成功的概率(找到與q臨近的p):

定向查詢探測(cè)序列(Query-Directed Probing Sequence)

構(gòu)造探測(cè)序列的一個(gè)最原始的方法是，對(duì)所有可能的微擾向量通過(guò)上面的公式計(jì)算分?jǐn)?shù)并進(jìn)行排序。但是凳厢，有L(2^M-1)個(gè)微擾向量柬焕，我們只希望使用其中很小的一部分。所以棠隐，顯式地生成所有的微擾向量看上去沒(méi)有必要，也是浪費(fèi)的檐嚣。接下來(lái)助泽，我們描述一個(gè)按照分?jǐn)?shù)升序排列生成微擾向量的更加有效的方法。
首先嚎京，我們注意到微擾向量Δ的分?jǐn)?shù)依賴于Δ中非零坐標(biāo)嗡贺，所以，分?jǐn)?shù)較低的微擾向量只含有幾個(gè)非零坐標(biāo)項(xiàng)鞍帝。在生成微擾向量時(shí)诫睬，我們使用(i,δi)對(duì)的集合形式來(lái)表示非零的坐標(biāo)項(xiàng)。(i,δ)表示對(duì)于q的哈希值的第i個(gè)坐標(biāo)加上δ項(xiàng)*帕涌。
給定查詢數(shù)據(jù)q和哈希函數(shù)hi摄凡，我們首先計(jì)算xi(δ)续徽，其中i=1,...,M，δ∈{-1,+1}亲澡。我們將這2M個(gè)值按升序排列钦扭，我們令zj表示為排序序列的第j個(gè)元素，如果zj=xi(δ)床绪，那么令πj=(i,δ)土全，所以xi(δ)是升序排列中第j小的元素。這里滿足xi(-1)+xi(+1)=W会涎，如果πj=(i,δ),那么π2M+1-j=(i,-δ)裹匙。
現(xiàn)在，我們將微擾向量看做是{1,...,2M}的子集末秃，稱為擾動(dòng)集(pertubation set)概页。對(duì)于一個(gè)擾動(dòng)集A，微擾向量ΔA是從擾動(dòng)集中得到的坐標(biāo)集合{πj|j∈A}练慕。
每個(gè)擾動(dòng)集A都可以算一個(gè)分?jǐn)?shù)

• shift(A)：該步驟是將max(A)換成1+max(A),比如shift({1, 3, 4}) = {1, 3, 5}
• expand(A)：該步驟是為集合A增加一個(gè)元素1+max(A)，比如expand({1, 3, 4}) = {1, 3, 4, 5}

產(chǎn)生擾動(dòng)集的算法

min-heap是用于維護(hù)微擾向量候選集的劲阎，父集的分?jǐn)?shù)不大于子集的分?jǐn)?shù)绘盟。
該堆(heap)被初始化為集合{1}，每次我們刪除頂端節(jié)點(diǎn)(集合Ai)悯仙，生成兩個(gè)新的集合shift(Ai)和expand(Ai)龄毡。僅輸出有效的頂端節(jié)點(diǎn)Ai。
該過(guò)程如下圖所示：

對(duì)于j=1,...,M锡垄，πj和π2M+1-j是同一坐標(biāo)的相反的擾動(dòng)沦零，一個(gè)有效的擾動(dòng)集A至多只能有{j,2M+1-j}中的一個(gè)元素。
shift和expand操作還有兩個(gè)性質(zhì)：

1. 對(duì)于一個(gè)擾動(dòng)集A货岭，shift(A)和expand(A)的分?jǐn)?shù)要比A的分?jǐn)?shù)大
2. 對(duì)于任意一個(gè)擾動(dòng)集A路操，shift和expand操作得到的序列是唯一的

小結(jié)

為了簡(jiǎn)化以上闡述，我們通過(guò)產(chǎn)生對(duì)于單一哈希表的擾動(dòng)集的過(guò)程來(lái)更加細(xì)致的說(shuō)明千贯。
對(duì)于每個(gè)哈希表屯仗，我們維護(hù)由(i,δ)和zj構(gòu)成的排序的清單，同時(shí)丈牢，還維護(hù)一個(gè)為所有哈希表生成擾動(dòng)集的堆(a single heap)祭钉。該堆里每個(gè)候選的擾動(dòng)集都對(duì)應(yīng)一個(gè)哈希表t瞄沙，當(dāng)集合A和表t關(guān)聯(lián)并從堆中去掉時(shí)己沛，新生成的shift(A)和expand(A)也與表t關(guān)聯(lián)起來(lái)慌核。

轉(zhuǎn)載請(qǐng)注明作者Jason Ding及其出處
Github博客主頁(yè)(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡(jiǎn)書主頁(yè)(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
百度搜索jasonding1354進(jìn)入我的博客主頁(yè)