金悅祺, 胡紅鋼

中國科學(xué)院 電磁空間信息重點實驗室, 合肥230027

1 問題介紹

1.1 格密碼

隨著量子計算的深入研究, 越來越多的高性能量子算法被提出, 這使得某些傳統(tǒng)的密碼體系在未來的量子手段下不堪一擊. 比如著名的Shor 算法就能夠在多項式時間分解大整數(shù), 從而攻破目前廣泛應(yīng)用的RSA 公鑰體系. 基于格的密碼體系具有對抗量子計算攻擊的能力, 因此在近些年受到人們的廣泛關(guān)注. 眾所周知, 許多密碼體系都是基于困難問題建立的. 在格中, 最短向量問題(shortest vector problem, SVP)就是一個很著名的NP-Hard 問題[1], 因此對它的研究至關(guān)重要.

1.2 尋找短向量

至今為止, 在尋找短向量方面已經(jīng)有了很多種方法. 例如枚舉[2,3],(啟發(fā)式)篩法[4–6], 以及Micciancio 提出的構(gòu)造Voronoi 網(wǎng)格法[7], 還有2014 年提出的基于高斯采樣的方法[8]等等. 枚舉法從字面意思理解就可以看出它具有很高的時間復(fù)雜度(2Θ(nlog(n))), 但是其空間復(fù)雜度很低(poly(n)). 篩法通?；趩l(fā)式假設(shè), 具有相對較低的時間復(fù)雜度(2Θ(n)), 較高的空間復(fù)雜度(2Θ(n)), 以及較大的常數(shù)因子. 從理論上來講, 在漸進(jìn)意義下, 啟發(fā)式篩法應(yīng)該在時間上優(yōu)于枚舉法, 但是在目前的實踐中, 相比于應(yīng)用了高效剪枝的枚舉, 篩法仍然要慢一些[9].

1.3 篩法

2008 年, Nguyen 與Vidick 提出了第一個啟發(fā)式篩法(NV-Sieve)[5], 這是在SVP 問題中第一次引入啟發(fā)式假設(shè)的解法. 雖然其效果不佳, 原始版本僅能解決不到50 維的SVP 問題, 但是它為解決SVP問題提供了一個新的思路. 2010 年, Micciancio 提出了一種新的篩法(GaussSieve)[6], 從實踐角度來講,它的表現(xiàn)非常出色, 以至于后續(xù)許多人的優(yōu)化版本都是以該方法為基礎(chǔ)的[10–14].

1.4 位置敏感哈希LSH

位置敏感哈希(locality-sensitive hashing,LSH)是在解決近鄰搜索問題(nearest neighbor searching,NNS)[9]中提出的. 它的思路是保留敏感信息, 模糊其余信息, 使得具有相同敏感信息的向量獲得同樣的哈希值. 這里的敏感信息可以理解為距離、角度等等. 在搜索近鄰的時候, 只需要搜索與目標(biāo)向量具有相同哈希值的向量即可. 通過計算哈希值, 降低搜索成本, 這個思路在篩法中也是可以應(yīng)用的.

1.5 篩法與LSH

2015 年, Laarhoven 提出了對于篩法的一種優(yōu)化[15], 其中第一次引入了LSH. 在篩法中引入LSH,效果是顯著的, 但是最初的Spherical LSH 似乎并不適用于GaussSieve, 只能用于NV-Sieve, 所以其實用性并不高. 后續(xù)他又使用Angular LSH[16]、Cross-Polytope LSH[17]來加速GaussSieve, 得到了更好的效果.

1.6 我們的結(jié)果

在本文中, 我們將K-Means LSH 引入GaussSieve, 對其進(jìn)行了優(yōu)化, 提高了其效率. 額外引入一個可調(diào)整的參數(shù), 我們提高了其使用的靈活性.

2 預(yù)備知識

2.1 格

這里先介紹一下格的基礎(chǔ)知識. 所謂格, 一句話描述, 就是Rn下離散的加法子群. 但是通常來說, 我們研究的是Zn下的加法子群, 也就是由整點構(gòu)成的格. 我們定義L = L(B) 是由格基B ={b1,b2,··· ,bn} 生成的格, 即L(B) = {Bx|x ∈Zn}. 定義格的體積vol(L(B)) = det(B), 最短非零向量λ1(B)=λ1(L(B)).

2.2 近鄰搜索問題

近鄰搜索問題NNS 定義為: 給定向量集合L, 給定一個目標(biāo)向量v /∈L, 希望找到向量v0∈L 滿足d(v,v0) 最小. 如果在低維度的情況下, 向量集合L 的大小為N, 那么通過數(shù)據(jù)結(jié)構(gòu)的優(yōu)化與預(yù)處理, 可以在O(log(N)) 時間內(nèi)進(jìn)行查詢. 但是放到高維空間, 隨著維數(shù)n 增大, 似乎暴力搜索變成了復(fù)雜度最低的方法, 這個就是著名的“維數(shù)災(zāi)難(curse of dimensionality)” 現(xiàn)象[9].

為了解決這個問題, 我們希望將L 轉(zhuǎn)化為哈希桶的結(jié)構(gòu), 使得對于特定的一個桶中的所有向量vi滿足d(vi,v) <= r1, 而對于其余桶中的所有向量vi滿足d(vi,v) >= (1+?)r1, 這樣我們就可以只遍歷一個桶中的向量從而得到結(jié)果. 這個方法看上去很完美, 但是它只是理想情況下的方法. 實際上, 人們通常是使用LSH 得到近似結(jié)果.

2.3 LSH

一個LSH 是一個函數(shù)族, 類似于傳統(tǒng)的hash 函數(shù), 它也是將定義域中的向量映射為一個散列值. 不同于傳統(tǒng)的hash 函數(shù)的地方在于, LSH 會把相似的向量映射為同一個散列值, 而把不相似的向量映射為不同的散列值. 不妨設(shè)函數(shù)D 是衡量向量相似程度的函數(shù), 那么我們有下面的定義:

定義1[9]一個函數(shù)族H = h:Rn→U 定義為在相似函數(shù)D 下具有(r1,r2,p1,p2)-敏感的LSH,如果它滿足對于任意的v,w ∈Rn, 下面兩式成立:

(1) 如果D(v,w)≤r1, 那么Ph∈H[h(v)=h(w)]≥p1.

(2) 如果D(v,w)≥r2, 那么Ph∈H[h(v)=h(w)]≤p2.

根據(jù)定義我們也可以看出來, 為了明顯地區(qū)別v 和w, 我們希望p1?p2. 然而如果r1和r2比較接近, 那么我們很難滿足上面的需求. 因此可以考慮使用多個函數(shù)進(jìn)行比較, 這也是LSH 是一族函數(shù)而非一個函數(shù)的用意. 為了放大p1與p2的差距, 下面兩個操作是至關(guān)重要的[9].

AND. k 個不同的哈希函數(shù)h1,h2,··· ,hk的AND 操作定義為一個函數(shù)h′:Rn→Uk, 其中h′(v)的第j 維坐標(biāo)即為hj(v), 我們定義h′(v)=h′(u) 當(dāng)且僅當(dāng)對于任意i ∈{1,2,··· ,k} 有hi(v)=hi(u).這樣任取k 個哈希函數(shù)就構(gòu)成了一個新的LSH, 它是(d1,d2,pk1,pk2) 敏感的.

OR. t 個不同的哈希函數(shù)h1,h2,··· ,ht的OR 操作定義為一個函數(shù)h′: Rn→Ut, 其中h′(v) 的第j 維坐標(biāo)即為hj(v), 我們定義h′(v) = h′(u) 當(dāng)且僅當(dāng)存在某個i ∈{1,2,··· ,t} 有hi(v) = hi(u).這樣任取t 個哈希函數(shù)就構(gòu)成了一個新的LSH, 它是(d1,d2,1 ?(1 ?p1)t,1 ?(1 ?p2)t) 敏感的.

在LSH 中任意選取kt 個不同的函數(shù),通過AND 和OR 操作,就能得到一族(d1,d2,1?(1?pk1)t,1?(1 ?pk2)t) 敏感的LSH, 注意到如果p1>p2, 那么就有1 ?(1 ?pk1)t>>1 ?(1 ?pk2)t, 這就得到了我們想要的LSH. 對于k 和t 的選取, 我們有下面的定理:

定理1[9]對于一個(r1,r2,p1,p2) 敏感的LSH 函數(shù)族H, 以及一個大小為N 的向量集合L, 令

對于給定的向量v, 下面兩條結(jié)論很有可能至少有一條會滿足:

(a) 能夠找到向量w ∈L 滿足D(v,w)≤r2;

(b) 不存在向量w ∈L 滿足D(v,w)>r1.

其復(fù)雜度為:

(1) 對于列表L 的預(yù)處理時間: ?O(kN(1+ρ));

(2) 預(yù)處理之后列表的空間復(fù)雜度: ?O(N(1+ρ));

(3) 對于給定v 的一次查詢: ?O(Nρ).

2.4 K-Means LSH

本文中主要依賴的LSH 是K-Means LSH, 其中的K-Means 最早是機(jī)器學(xué)習(xí)中的最常用的聚類算法[18], 之后Lo?c Paulevé 等人根據(jù)該想法設(shè)計了K-Means LSH[19]. 對于固定的一個K 值, 一個KMeans LSH 函數(shù)族H 中的每個函數(shù)h 可以描述為:

選取K 個不同的向量構(gòu)成集合C ={ci|i=1,2,··· ,K}

點集C 通常稱作中心點集. 那么通過構(gòu)造不同的C 就可以得到哈希函數(shù)族H. 其具體的敏感度與點集C 的選取有關(guān). 在機(jī)器學(xué)習(xí)中, 中心點集一般是通過隨機(jī)選取數(shù)據(jù)集中的點, 然后進(jìn)行迭代的方式得到的, 例如著名的SIFT 算法[20]. 在這里, 我們啟發(fā)式地假設(shè)格點在空間中分布是均勻的, 因此我們只需要使C 中的點的分布盡可能均勻即可. 下面是啟發(fā)式假設(shè):

假設(shè)1 在格中均勻隨機(jī)取兩個向量v 和w, 其角度Θ(v,w) 與在單位球中均勻隨機(jī)選取v 和w 得到的角度分布相同.

通俗地理解, 啟發(fā)式假設(shè)意思是說Rn中的格點分布可以看做是均勻的. 然而, 這個均勻的意思與二三維空間并不一樣. 事實上, 在高維空間中, 隨機(jī)取兩個點v 和w, 那么他們的角度Θ(v,w) 很有可能非常接近π/2, 而并不是通俗理解的[0,π] 中的均勻隨機(jī)值. 隨著維度的增高, 這個趨勢會越發(fā)明顯.

2.5 GaussSieve

2010 年, Micciancio 等人提出了一種新的篩法[6], 其思路類似于Gauss 在約簡二維格基時采用的方法, 因此命名為GaussSieve. 該算法偽代碼見算法1.

算法1 GaussSieve(B) [6]Input: 經(jīng)過LLL 約簡的格基B Output: 格中的短向量v 1 Function GaussSieve(B,μ):18 Function GaussReduce(v,L,S):2 Initialize L = {0},S = {},K = 0;3 while K ≤c do 19 while ?vi ∈L :20 ∥vi∥≤∥v∥∧∥v ?vi∥≤∥v∥do 4 if S ?= ?then 5 vnew = S.pop();6 else 7 vnew = SampleGaussian();21 v = v ?vi;22 end 23 while ?vi ∈L :24 ∥vi∥≥∥v∥∧∥vi ?v∥≤∥vi∥do 8 end vnew = GaussReduce(vnew,L,S);10 if vnew = 0 then 9 11 K = K +1;12 else 25 L = L{vi};26 S.push(vi ?v);27 end 28 Return v;29 End Function 13 L = L ∪{vnew};14 end 15 end 16 Return L 中最短向量;17 End Function

該算法的主要空間復(fù)雜度是棧S 和列表L 的大小, 主要空間復(fù)雜度是從L 中查找能約化向量的時間. 因此, 從減小時間復(fù)雜度的角度來考慮, 利用LSH 來加快查找速度是一個不錯的想法.

對于兩個向量u 和v, 如果∥u ?v∥≤∥u∥或者∥u ?v∥≤∥v∥, 那么顯然有Θ(u,v)≤π/3, 反之則有Θ(u,v) > π/3. 看上去似乎不好區(qū)分兩種情況, 但是事實上, 在高維空間中, 能夠約化的向量對大概率滿足Θ(u,v) = π/3, 不能約化的向量對大概率滿足Θ(u,v) = π/2. 我們曾經(jīng)做過一個實驗, 對于50 維的空間, 隨機(jī)選取向量對u 和v, 那么Θ(u,v) 有超過99% 的幾率落在區(qū)間[85°, 95°] 中. 所以我們只需要選取形如(π/3,π/2,p1,p2) 的LSH 即可. 即我們考慮用

來代替

進(jìn)行判定.

在上面的討論中, 對于我們選取的參數(shù)為(π/3,π/2,p1,p2) 的LSH, 我們實際上只需要關(guān)心它的參數(shù)r1= π/3. 對于第二個參數(shù)r2= π/2, 實際上只是表明該LSH 能夠區(qū)分夾角小于r1= π/3 與夾角接近r2= π/2 的向量對. 嚴(yán)格來說, 可以改寫參數(shù)為r2= π/2 ?δ 使我們的表述更加嚴(yán)謹(jǐn), 其中δ << r2為一個常數(shù). 對應(yīng)的, p2也會增加一個可以忽略的常數(shù), 這是因為高維空間中隨機(jī)選取的向量對幾乎都具有接近0 的內(nèi)積, 即夾角會大于r2= π/2 ?δ. 這些向量對是不能約化的, 因此利用具有r1= π/3 參數(shù)的LSH 能夠幫助我們篩選出能夠約化的向量對, 從而達(dá)到加速算法的目的.

3 應(yīng)用LSH 的GaussSieve

3.1 算法描述

結(jié)合上面介紹的內(nèi)容, 很自然的考慮用Θ(u,v) 來估算是否可以對u 和v 進(jìn)行約簡, 引入LSH 來估算Θ(u,v) 的大小. 于是考慮用一組哈希桶Ti代替GaussSieve 中的列表L, 用同一個哈希桶中的搜索取代原算法中對列表L 進(jìn)行蠻力搜索的步驟, 得到算法2[16].

算法2 GaussSieve-with-LSH(B) [16]Input: 經(jīng)過LLL 約簡的格基B Output: 格中的短向量v 1 Function GaussSieve-with-LSH(B,μ):21 Function GaussReduce-with-LSH(v,L,S):2 Initialize L = {0},S = {},K = 0;3 Initialize k ?t random hash functions hi,j ∈H;4 Initialize t empty hash tables Ti;5 while K ≤c do 22 C = ∪t i=1 Ti[hi(v)];23 while ?vi ∈C :24 ∥vi∥≤∥v∥∧∥v ?vi∥≤∥v∥do 6 if S ?= ?then 7 vnew = S.pop();8 else 25 v = v ?vi;26 end 27 while ?vi ∈C :28 ∥vi∥≥∥v∥∧∥vi ?v∥≤∥vi∥do vnew = SampleGaussian();10 end 11 vnew=GaussReduce?with?LSH(vnew,L,S);12 if vnew = 0 then 9 13 K = K +1;14 else 29 L = L{vi};30 Delete v from all hash tables;31 S.push(vi ?v);32 end 33 Return v;34 End Function 15 L = L ∪{vnew};16 Insert v to all hash tables Ti;17 end 18 end 19 Return L 中最短向量;20 End Function

其實相比于以往的此類算法, 他們的框架(算法2) 都是相同的, 區(qū)別只在于LSH 的具體形式.

3.2 K-Means LSH

根據(jù)2.4 節(jié)中介紹的內(nèi)容明顯能看出來, 我們希望中心點集的分布盡可能均勻, 例如K =2n 的時候,取中心點集為C = {±ei} 或其一個旋轉(zhuǎn). 但是事實上, 對于高維空間, 這是一個名叫Tammes 的困難問題[21], 考慮到我們求解的格至少有50 維, 在這樣的維度下求解Tammes 問題并不可行. 那么我們退而求其次, 我們隨機(jī)選取K 個點組成中心點集C, 對于某個固定的角度α, 下式成立

上式通俗的理解就是希望C 中的點盡量相互遠(yuǎn)離. 為此, 我們設(shè)計了一個很簡單的算法可以實現(xiàn)這個目標(biāo), 即算法3.

算法3 很簡單, 而且作為篩法的預(yù)處理步驟, 我們并不需要過多的關(guān)注它的復(fù)雜度, 這一切似乎都很完美. 然而事實上, 如果假設(shè)α = π/2, 明顯最優(yōu)解是|C| = 2n, 但是如果使用算法3, 甚至連n 個點都很難取出來. 萬幸的是, 雖然對于任意維度, 在α = π/2 下的最優(yōu)解都是|C| = 2n, 但是隨著α 的減小, 例如α = 80?,70?, 那么通過算法3 得到的|C| 與維度n 至少是指數(shù)級的關(guān)系, 這個在文獻(xiàn)[12] 中有詳細(xì)的描述. 特別的, 我們?nèi)绻ˇ?π/3, 在n=10 的情況下, 利用算法3 得到的|C|≥104. 對于α=π/3 的情況, 文獻(xiàn)[5] 的結(jié)論告訴我們至多存在20.2075n個兩兩夾角大于α 的向量, 而在實際使用中, 我們只需要取K = kn 個中心點集. 因此, 在本文的主要算法中, 使用這個簡單的取樣算法是合理的. 得到中心點集后, 就可以根據(jù)(1)式計算出hash 值以完成算法2.

算法3 Central point set sampling Input: 最小角度α Output: 中心點集C 1 Const 最大碰撞次數(shù)m;2 Initialize C = {}, 當(dāng)前碰撞次數(shù)k = 0;3 while k ≤m do k = k+1;7 else 4 p = Simple_on_Unitsphere();5 if ?p0 ∈C : Θ(p,p0) ≤α then 6 8 Insert p into C;k = 0;10 end 11 end 12 Return C;9

3.3 與CP-Sieve 對比

先回憶一下CP-Sieve 中使用的Cross-Polytope LSH[22], 其哈希函數(shù)為

其正負(fù)號等于絕對值最大坐標(biāo)的符號. 然后將這個哈希函數(shù)拓展為一族哈希函數(shù)

其中A 是滿足每一個元素ai,j～N[0,1] 的矩陣, N[0,1] 表示[0,1] 上的正態(tài)分布. 現(xiàn)在讓我們從幾何的角度理解一下這一族函數(shù): 顯然h 的取值跟v 的模長無關(guān), 所以不妨將其看成是單位球面上的哈希函數(shù),A 可以看做是旋轉(zhuǎn)矩陣. 因此其幾何含義便是找到C = {±ei} 中距離目標(biāo)v 最近的點, 其函數(shù)族即為對C 進(jìn)行了旋轉(zhuǎn)A?1.

因此我們可以看出, Cross-Polytope LSH 是K-Means LSH 在α = π/2 時的最優(yōu)解, 可以看做是K-Means LSH 的一種特殊情況. 相比于Cross-Polytope LSH, K-Means LSH 可以通過更大的C 以及更小的α 來提高其精確度.

對于Cross-Polytope LSH, 文獻(xiàn)[23] 中給出了其單次的精確程度, 如下引理

引理1 記H 為Cross-Polytope LSH 函數(shù)族, 記θ =Θ(u,v) 為兩個向量u 和v 的夾角, 那么對于較大的n, 有下式成立

雖然這個引理看上去結(jié)果很漂亮, 但是事實上, 在我們的應(yīng)用范圍內(nèi), 即維數(shù)n 相對比較小的時候,O(log log n) 對于性能的影響是相當(dāng)大的. 例如在n=50 的時候, CP-LSH 的實驗結(jié)果顯示其p1≈3.5%,p2≈1%, 這與引理1 去掉O(log log n) 的結(jié)果相去甚遠(yuǎn). 在實踐中, K-Means LSH 的表現(xiàn)相對優(yōu)秀一些,針對這方面的對比, 我們會在后面進(jìn)行展示.

從計算hash 值的復(fù)雜性上對比, CP-LSH 的計算過程是旋轉(zhuǎn)O(n2) 與尋找最大坐標(biāo)O(n), 通過尋找特殊形式的旋轉(zhuǎn)矩陣A, 可以將旋轉(zhuǎn)的復(fù)雜度降為O(n log n). K-Means LSH 的計算過程是計算K 個內(nèi)積O(Kn) 與尋找最大值O(K), 考慮到K 的大小一般正比于n, 因此其復(fù)雜度也是O(n2), 這與未經(jīng)優(yōu)化的CP-LSH 復(fù)雜度相同. K-Means LSH 在復(fù)雜度上還有優(yōu)化空間, 這是一個開放性問題.

另外, Thijs Laarhoven 提出了一種步進(jìn)式的優(yōu)化[14], 能夠提高框架(算法2) 的性能, 也可以對本算法進(jìn)一步優(yōu)化.

4 實驗結(jié)果

本文中提到的K-Means-LSH 與機(jī)器學(xué)習(xí)中聚類分析使用的同名LSH 并不完全相同, 這是因為聚類分析中是根據(jù)已有的固定的樣本點通過迭代的方式生成中心點集, 而本文針對的是球面上均勻分布的點確定中心點集, 相比前者, 該方法更像對球面的均分, 這與文獻(xiàn)中提到的Angular-LSH 和CP-LSH 的目的是一樣的. 為了觀察K-Means-LSH 能否適應(yīng)這個目的, 本節(jié)中前兩小節(jié)先對該LSH 進(jìn)行一些實驗測試.

4.1 不同K 值對應(yīng)LSH 的性能對比

本節(jié)中, 我們觀察不同K 值對于LSH 性能的影響, 從而在后面的分析中選擇更合適的LSH. 在這里, 我們只考慮單個LSH 的結(jié)果. 對于單個LSH 而不是LSH 函數(shù)族, CP-LSH 的復(fù)雜度是O(n), 因為不需要進(jìn)行旋轉(zhuǎn), 從均勻取樣的角度來看, 只需要尋找最大的坐標(biāo)分量即可, 然而K-Means-LSH 的復(fù)雜度是O(Kn). 受限于計算能力, 我們只在中維度(n ∈[30,70]) 進(jìn)行觀察. 為了結(jié)果的準(zhǔn)確性, 我們?nèi)×藃2=85°. 結(jié)果如圖1.

由于該LSH 的具體性能受中心點集位置的影響, 而均勻布點又是困難問題, 所以這里只能通過多次試驗給出數(shù)值模擬, 具體的理論值有待研究.

圖1 記錄了該實驗的結(jié)果. 看起來似乎違背了我們的直覺, 隨著K 的增大, 參數(shù)p1有明顯的的下降趨勢. 事實上, 回到定義, 實驗中的p1表示的是下式的值:

那么我們考慮哈希值不同且夾角小于π/3 的向量對, 這樣的向量對會出現(xiàn)在兩個中心點“控制范圍” 的邊界附近一定范圍內(nèi)(中心點p 控制范圍指的是集合{u : Θ(u,p) ≤minp′?=pΘ(u,p′)}, 其邊界附近的一定區(qū)域可以用集合?p= {u : minp′?=pΘ(u,p′)?δp≤Θ(u,p) ≤minp′?=pΘ(u,p′)} 來表示, 其中δp是常數(shù)). 隨著K 的增大, 這些區(qū)域的并集∪p?p會具有更大的面積, 從而導(dǎo)致p1的下降.

4.2 K-Means-LSH 與CP-LSH 的性能對比

本節(jié)中, 我們來對比兩種不同的LSH 在不同維度下的p1與p2值, 以此反映兩種LSH 的性能. 考慮到實際應(yīng)用, 我們?nèi)∷惴? 中的α=π/3, 結(jié)果如圖2(a).

從實踐結(jié)果上來看, K-Means LSH 的效果要明顯優(yōu)于CP-LSH. 當(dāng)K = N 時, 值p1與p1/p2都是K-Means-LSH 更優(yōu). 當(dāng)K = 2N 時, 兩種LSH 具有相似的p2值, 這很好理解, 因為CP-LSH 就是均勻情況下的K-Means-LSH. 然而, K-Means-LSH 的p1值遠(yuǎn)大于CP-LSH. 這種情況隨著維數(shù)的增加表現(xiàn)的更明顯, 因為在高維, 隨機(jī)取兩個向量, 它們之間的夾角有很大概率接近π/2, 在這種情況下, 由于中心點集的不均勻會造成某些局部中心點比較密集, 這個子中心點集能夠過濾接近但是小于π/2 的點對, 從而提高p1值. 隨著K 的增大, K-Means-LSH 的p1會降低, p2也會略微降低, 但是p1/p2會升高(如圖2(b)).

4.3 K-Means Sieve 性能測試

本節(jié)中, 我們將對使用了K-Means-LSH 的GaussSieve 進(jìn)行測試. 本算法涉及三個參數(shù): AND 操作次數(shù)k、OR 操作次數(shù)t、中心點集大小K. 根據(jù)定理1 與文獻(xiàn)[17], 考慮到兩種LSH 的參數(shù)p1與p1/p2對比, 我們?nèi) = 30, 對不同的K, 在維度[35,70] 之間測試其漸進(jìn)復(fù)雜度. 在這里, 為了排除計算機(jī)性能對于算法的干擾, 我們先同文獻(xiàn)[17] 一樣, 考慮Operations 參數(shù)(這里Operations = Comparisons +Hashes, 第一項表示比較兩個向量能否約減的次數(shù), 第二項表示計算hash 值的次數(shù)). 測試結(jié)果如圖3(圖中的小數(shù)表示直線的斜率):

從圖3 可以看出, 我們的算法在具體復(fù)雜度的數(shù)值上略低于CP-Sieve, 這是因為CP-LSH 在計算量上相當(dāng)于K = N 的K-Means LSH, 但是由于中心點集分布不均勻, 在K = N 的時候效率比CPSieve 差. 但是從漸進(jìn)復(fù)雜度的角度來看, 我們的算法是有優(yōu)勢的, 隨著K 的增加, 漸進(jìn)復(fù)雜度是優(yōu)于CP-Sieve 并且還有下降空間的. 更重要的是, 上面采用Operations 作為比較參數(shù)其實并不是很合適, 因為計算一次Comparison 需要進(jìn)行O(n) 次運算(加法與乘法), 而計算一次hash 需要進(jìn)行O(n2) 次運算(CP-LSH 需要計算一次旋轉(zhuǎn), K-Means LSH 需要計算K = kn 次內(nèi)積), 因此這里我們考慮使用參數(shù)Complexity=Comparisons+Hashes2來衡量其復(fù)雜度, 測試結(jié)果如圖4(圖中的小數(shù)表示直線的斜率):

從圖4 中可以看出, 在Complexity 參數(shù)下, 無論是在漸進(jìn)復(fù)雜度意義下還是具體數(shù)值下, 我們的算法都是有優(yōu)勢的.

綜合來看, 我們的算法相比于現(xiàn)有的CP-Sieve 是有優(yōu)勢的, 不僅僅是因為復(fù)雜度上的優(yōu)勢, 更因為我們的算法多一個參數(shù)K, 使得在實際應(yīng)用中有更大的選擇空間, 對于較低維度的空間, 可以不考慮漸進(jìn)復(fù)雜度以獲得更優(yōu)的時間性能, 而對于高維空間, 可以通過增大K 以獲得更好的Operation 意義下的漸進(jìn)復(fù)雜度(這點從圖中能看出, 對于固定的k, 增大參數(shù)K 的值能明顯優(yōu)化其漸進(jìn)復(fù)雜度).

由于Tammes 問題的復(fù)雜性, 對于高維空間, 我們甚至無法對均勻布點的個數(shù)進(jìn)行估計, 從算法3 測試的結(jié)果來看, 它至少是指數(shù)級別的. 從實驗結(jié)果上來看, 對于略高維度的空間, 增大K 的效果是明顯的,這就說明中心點集與維度n 之間的關(guān)系在最優(yōu)情況下很可能不是線性的. 因此, 中心點集的大小或許可以進(jìn)一步優(yōu)化. 除此之外, 它還有兩個很大的優(yōu)化空間: 一是能否通過選取特定形式而又不失均勻性的中心點集, 以達(dá)到降低計算hash 值復(fù)雜度的目的; 二是優(yōu)化中心點集的均勻性, 以提高其性能.

總的來說, CP-Sieve 可以看做是本方法的特殊情況. 受限于Tammes 問題, K-Means Sieve 的潛力并沒有被完全地挖掘出來. 考慮到K-Means LSH 性能優(yōu)秀, 我們完全有理由相信, 當(dāng)中心點集足夠均勻的情況下, K-Means Sieve 會有更好的結(jié)果.