王忠偉，陳葉芳，錢江波，陳華輝

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江寧波315211）

基于LSH的高維大數(shù)據(jù)k近鄰搜索算法

王忠偉，陳葉芳，錢江波，陳華輝

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江寧波315211）

局部敏感哈希（LSH）及其變體是解決高維數(shù)據(jù)k近鄰（kNN）搜索的有效算法.但是，隨著數(shù)據(jù)規(guī)模的日趨龐大，傳統(tǒng)的集中式LSH算法結(jié)構(gòu)已經(jīng)不能夠滿足大數(shù)據(jù)時(shí)代的需求.本文分析傳統(tǒng)LSH方案的不足之處，拓展AND-OR結(jié)構(gòu)，提出通過(guò)索引而不比較原始數(shù)據(jù)直接實(shí)現(xiàn)高維大數(shù)據(jù)k近鄰搜索算法C2SLSH.理論分析和實(shí)驗(yàn)證明，C2SLSH在分布式平臺(tái)下具有穩(wěn)定的可擴(kuò)展性，在保證同等精確率的情況下，處理速度大約是現(xiàn)有方法的3倍.

高維數(shù)據(jù)k近鄰；局部敏感哈希；MapReduce；沖突計(jì)數(shù)排序

1 引言

隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，數(shù)據(jù)，尤其是高維數(shù)據(jù)呈爆炸式增長(zhǎng)［1～3］.從這些海量數(shù)據(jù)中搜索近似對(duì)象是很多應(yīng)用的關(guān)鍵，如近似檢索、推薦系統(tǒng)、k近鄰問(wèn)題等.通過(guò)構(gòu)造索引，如R-tree［4］、K-D tree［5］等，可快速找到查詢對(duì)象的近鄰或近似對(duì)象.然而，隨著數(shù)據(jù)維度的增加，這些算法的效率大幅度降低.當(dāng)維度大于10的時(shí)候，這些方法甚至比線性掃描方法還慢，這種現(xiàn)象被稱為“維度災(zāi)難”［6］.局部敏感哈希（LSH，Locality Sensitive Hashing）是由 Indyk和Motwani提出的一種高維索引結(jié)構(gòu)［7］，它的基本思想是針對(duì)數(shù)據(jù)對(duì)象集，利用一組特定的哈希函數(shù)來(lái)建立哈希表.使得在一定的相似度量條件下，相似對(duì)象映射到相同的區(qū)域的概率大于非相似對(duì)象.LSH及其變體［8～11］可以將相似的對(duì)象以高概率映射到同一個(gè)桶中，并通過(guò)解決近似最近鄰的方法來(lái)替代解決精確近鄰問(wèn)題，是處理高維數(shù)據(jù)近似問(wèn)題的有效算法.

然而，隨著大數(shù)據(jù)時(shí)代的到來(lái)，“維度災(zāi)難”和數(shù)據(jù)規(guī)模兩個(gè)問(wèn)題疊加，使得k近鄰查詢問(wèn)題變得非常困難，傳統(tǒng)的集中式LSH算法結(jié)構(gòu)已經(jīng)不能夠滿足需求.目前Hadoop平臺(tái)［12］深受業(yè)界關(guān)注，它具有可擴(kuò)展、易使用、節(jié)點(diǎn)容錯(cuò)以及高可靠性等優(yōu)秀特性，適合處理大規(guī)模數(shù)據(jù).但是如果直接將局部敏感哈希及其變體應(yīng)用到該平臺(tái)，將不能充分發(fā)揮分布式平臺(tái)的優(yōu)勢(shì).本文在Hadoop分布式平臺(tái)下研究基于LSH的高維大數(shù)據(jù)kNN搜索算法，保證精確率和快速性，并減少了空間復(fù)雜度.

本文的貢獻(xiàn)如下：（1）提出適合分布式實(shí)現(xiàn)的AND-OR構(gòu)造方法，通過(guò)理論分析證明經(jīng)索引而不用比較原始數(shù)據(jù)可直接實(shí)現(xiàn)高維大數(shù)據(jù)k近鄰搜索；（2）充分考慮分布式計(jì)算的因素，緊密結(jié)合 MapReduce計(jì)算過(guò)程，在Hadoop分布式平臺(tái)上實(shí)現(xiàn)了所提出的算法；（3）真實(shí)數(shù)據(jù)集實(shí)驗(yàn)表明，所提出算法在分布式平臺(tái)上具有有效性和穩(wěn)定性，實(shí)驗(yàn)結(jié)果和理論分析的結(jié)論相一致.

2 相關(guān)工作

大數(shù)據(jù)處理面臨的一大挑戰(zhàn)是如何設(shè)計(jì)合適的索引結(jié)構(gòu)，從而能高效地完成近鄰搜索.雖然LSH是一種非常流行的高維數(shù)據(jù)處理算法，但是由于其對(duì)空間的依賴性較強(qiáng)，因此并不適合直接用來(lái)處理大數(shù)據(jù).有研究者改進(jìn)了LSH算法并在分布式平臺(tái)上應(yīng)用，但是相關(guān)的研究還比較少.

MIXED-LSH［13］把 LSH應(yīng)用到大數(shù)據(jù)集，在由多個(gè)節(jié)點(diǎn)組成的P2P分布式環(huán)境中實(shí)現(xiàn)了LSH算法.在分布式環(huán)境中實(shí)現(xiàn)LSH的一個(gè)簡(jiǎn)便方法是每個(gè)節(jié)點(diǎn)都保持相同的哈希表的數(shù)量.但是這會(huì)增加遠(yuǎn)程訪問(wèn)，因?yàn)樵S多節(jié)點(diǎn)要存取訪問(wèn)所有的哈希表.如果通信延遲是瓶頸的話，這種方法響應(yīng)時(shí)間會(huì)比較長(zhǎng).MIXED-LSH巧妙地使用為節(jié)點(diǎn)分配哈希桶的方法來(lái)減少遠(yuǎn)程訪問(wèn).特別地，MIXED-LSH把相關(guān)的哈希桶存儲(chǔ)在一起，分配到同一節(jié)點(diǎn)的哈希桶來(lái)自于不同的哈希表.由于這一策略的使用，在處理一個(gè)查詢?cè)L問(wèn)時(shí)，對(duì)于那些應(yīng)該被訪問(wèn)的對(duì)象，執(zhí)行MIXED-LSH索引方法可以一次訪問(wèn)多個(gè)哈希桶，從而減少了遠(yuǎn)程訪問(wèn)的頻率.MIXED-LSH重點(diǎn)在于解決分布式環(huán)境下所產(chǎn)生的網(wǎng)絡(luò)開(kāi)銷，其使用的距離度量是L1距離，很難有效的擴(kuò)展到其他距離度量的應(yīng)用.另外MapReduce和P2P是不同的分布式環(huán)境，不能遷移應(yīng)用.

LayeredLSH算法［14］是對(duì)EntroryLSH［15］的分布式改進(jìn)，可使用MapReduce框架實(shí)現(xiàn)計(jì)算過(guò)程.通過(guò)二次哈希把數(shù)據(jù)對(duì)象q存在某臺(tái)機(jī)器x上.查詢時(shí)，先給對(duì)象q一個(gè)小的偏移量，生成q+δi，把q和q+δi進(jìn)行二次哈希，根據(jù)它們對(duì)應(yīng)的哈希值，找到對(duì)應(yīng)的機(jī)器x，然后在機(jī)器x上執(zhí)行相似性搜索.通過(guò)采用二次哈希的策略，第一次哈希數(shù)據(jù)對(duì)象能哈希到同一個(gè)桶，那么第二次哈希會(huì)分布相同機(jī)器上，在Reduce階段給查詢對(duì)象一個(gè)偏移量，根據(jù)哈希值首先找到相應(yīng)桶對(duì)應(yīng)的機(jī)器，然后再進(jìn)行搜索.LayeredLSH保證了良好的負(fù)載平衡，但是這種方法是以更多的時(shí)間開(kāi)銷為代價(jià)的.另外，二次哈希也使得空間復(fù)雜度比傳統(tǒng)LSH算法更大.

雖然一些改進(jìn)的LSH方法在較小的數(shù)據(jù)集上能提供良好的過(guò)濾效果并且表現(xiàn)優(yōu)異，但是隨著數(shù)據(jù)集的增大，算法效果明顯降低.上述相關(guān)LSH的分布式算法沒(méi)有具體考慮假陽(yáng)性和假陰性的處理，會(huì)導(dǎo)致候選集的冗余度太大.另外，在得到候選集之后，從候選集獲取結(jié)果集的過(guò)程中，需要使用相應(yīng)的距離度量計(jì)算檢驗(yàn)候選集中每一個(gè)數(shù)據(jù)對(duì)象，此計(jì)算過(guò)程仍占據(jù)了查詢時(shí)間的主要部分，所以對(duì)于較大的數(shù)據(jù)集來(lái)說(shuō)，LSH算法的時(shí)間效率依然存在改進(jìn)的空間.本文提出的以沖突次數(shù)作為返回結(jié)果的測(cè)度，充分考慮AND-OR對(duì)假陽(yáng)性和假陽(yáng)性的控制，在保證結(jié)果正確率的情況下，有效的減少了查詢響應(yīng)的時(shí)間.

3 LSH及AND-OR構(gòu)造

定義1（LSH） 設(shè)S是距離度量dist的（數(shù)據(jù)）對(duì)象集合，d1、d2為距離度量dist的兩個(gè)距離.如果哈希函數(shù)族H中的每一個(gè)函數(shù)h滿足如下兩個(gè)條件，則哈希函數(shù)族H對(duì)于S中任意對(duì)象x和y稱為（dist1，dist2，p1，p2）-sensitive：

（1）如果d（x，y）≤dist1，那么Pr［h（x）=h（y）］≥p1；

（2）如果d（x，y）≥dist2，那么Pr［h（x）=h（y）］≤p2.

其中dist1＜dist2，p1＞p2∈［0，1］，Pr［］是概率.

LSH函數(shù)適合許多距離度量，其中l(wèi)P范式是基于p-stable分布的LSH函數(shù)族［16］.在這種情況下，對(duì)每一個(gè)高維數(shù)據(jù)對(duì)象v，哈希函數(shù)形式為

其中a是一個(gè)與v同維度的隨機(jī)向量集合，它的元素從p-stable分布中獨(dú)立選取，w是窗口長(zhǎng)度參數(shù)，b是從［0，w］中隨機(jī)選取的實(shí)數(shù).

從LSH的定義可以推出，使用一個(gè)哈希函數(shù)會(huì)產(chǎn)生假陽(yáng)性（False Positive）或假陰性（False Negative）錯(cuò)誤.假陽(yáng)性就是非相似的數(shù)據(jù)對(duì)象被哈希到相同的桶中，而假陰性就是真正相似的對(duì)象未能被哈希到相同的桶.為了提高LSH查詢的正確性，傳統(tǒng)LSH函數(shù)哈希族引入AND-OR構(gòu)造技術(shù)來(lái)改善［17］.AND構(gòu)造使得x 和y成為彼此的相似候選對(duì)象，當(dāng)且僅當(dāng)在所選同一組哈希函數(shù)計(jì)算結(jié)果同時(shí)相等.OR構(gòu)造使得x和y成為彼此的相似候選對(duì)象，當(dāng)且僅當(dāng)所選同一組哈希函數(shù)計(jì)算結(jié)果至少有一個(gè)相等.

傳統(tǒng)AND-OR構(gòu)造可以提高精確度，但是時(shí)空效率太低，主要是因?yàn)闃?gòu)造過(guò)程中使用了太多的哈希函數(shù)，計(jì)算量大且耗費(fèi)時(shí)間，存儲(chǔ)太多的對(duì)象副本也耗費(fèi)空間.另外，在獲得候選結(jié)果集之后，從候選集獲得結(jié)果集，需要計(jì)算真實(shí)相似度的集合往往也較大，使得計(jì)算時(shí)間延長(zhǎng).

4 沖突計(jì)數(shù)排序LSH

定理1 在相同次數(shù)LSH運(yùn)算中，如果兩個(gè)對(duì)象的距離越近，那么哈希到同一個(gè)桶的次數(shù)越多.

證明 根據(jù)定義1，對(duì)于兩個(gè)對(duì)象x，y，f（t）代表服從p-stable分布的概率密度函數(shù).設(shè)有該公式表明兩個(gè)對(duì)象x和y映射到同一個(gè)隨機(jī)向量區(qū)間的概率p（σ）與兩個(gè)對(duì)象的距離σ成反比，也就是說(shuō)，兩個(gè)對(duì)象距離越大獲得相同哈希值的概率越小.對(duì)于固定個(gè)數(shù)的哈希函數(shù)n，設(shè)其中沖突的個(gè)數(shù)是α（α＜n），那么如α的值越接近n，即兩個(gè)對(duì)象映射到同一個(gè)桶中的次數(shù)越多，則它們的相似度就越高.相反兩個(gè)對(duì)象相似度越低.證畢

根據(jù)定理1，kNN計(jì)算過(guò)程可分為兩個(gè)步驟：第一步，使用選定的多個(gè)哈希函數(shù)計(jì)算每個(gè)對(duì)象的哈希值，并映射到相應(yīng)的桶中；第二步，計(jì)算LSH沖突次數(shù).由于對(duì)象在LSH哈希空間下和原空間的距離是高概率等價(jià)的，所以使用LSH沖突次數(shù)來(lái)計(jì)算kNN可以得到正確的結(jié)果集.基于此，本節(jié)提出C2SLSH（Collision Counting Sorting LSH）算法結(jié)構(gòu).通過(guò)將對(duì)象之間產(chǎn)生的沖突次數(shù)進(jìn)行統(tǒng)計(jì)，并對(duì)結(jié)果正確性的影響進(jìn)行理論分析.

如前所述，給定一個(gè)（dist1，dist2，p1，p2）-sensitive的哈希函數(shù)族，可通過(guò)組合獲得一新的哈希函數(shù)族即給定一個(gè)（dist1，dist2，p1，p2）-sensitive的哈希函數(shù)族G，通過(guò)組合β個(gè)α-AND構(gòu)造（即一個(gè)β-OR構(gòu)造），可獲得一個(gè)新的（dist1，dist2，1-哈希函數(shù)族G′，如圖1所示.

C2SLSH對(duì)固定個(gè)數(shù)的哈希函數(shù)的結(jié)果進(jìn)行沖突次數(shù)統(tǒng)計(jì)并排序，間接實(shí)現(xiàn)了更高效的 α-AND構(gòu)造和β-OR構(gòu)造.也就是說(shuō)，C2SLSH算法實(shí)現(xiàn)的α-AND構(gòu)造是從n個(gè)LSH函數(shù)g1，g2，…，gn中任意選取α個(gè)組合而成的，這里的α（1≤α≤n）即是統(tǒng)計(jì)數(shù)；這種組合的個(gè)數(shù)共有種，即是β-OR構(gòu)造.在查找k近鄰結(jié)果的時(shí)候，首先在沖突次數(shù)最多的集合中尋找結(jié)果.如果結(jié)果不足k個(gè)，再改變?chǔ)恋娜≈?，每次減小1，一直找到k個(gè)結(jié)果并返回.根據(jù)定理1，對(duì)于C2SLSH算法的AND-OR方案，令u=p（σ）代表相似對(duì)象在一個(gè)哈希表中沖突的概率，假設(shè)這個(gè)過(guò)程中α的值改變了γ次，根據(jù)α和γ的取值，可以得出相似對(duì)象沖突的概率

通過(guò)計(jì)算，由圖2可知，當(dāng)n=20并給定一個(gè)較大的α值時(shí)，存在一個(gè)區(qū)間（0，t1）使得ε（u）接近0并且緩慢遞增；也存在一個(gè)相對(duì)應(yīng)的區(qū)間（t2，1）使得ε（u）接近1并且緩慢遞增.最終可以得到一個(gè)結(jié)論：ε（u）在區(qū)間［t1，t2］內(nèi)快速上升，并且ε（u）的快速上升區(qū)間會(huì)隨著α的遞減而緩慢向左移動(dòng)，也就是說(shuō)，我們可以通過(guò)改變?chǔ)恋闹祦?lái)改變?chǔ)牛╱）的快速上升區(qū)間，從而影響kNN查詢結(jié)果.

從上述理論分析過(guò)程也可以看出，C2SLSH算法之所以高效，有以下兩方面的原因：第一，由于數(shù)據(jù)對(duì)象經(jīng)過(guò)每個(gè)哈希函數(shù)計(jì)算之后就會(huì)對(duì)應(yīng)一個(gè)數(shù)據(jù)副本，我們?cè)谠O(shè)計(jì)AND-OR結(jié)構(gòu)時(shí)，使用了較少的LSH函數(shù)，因此C2SLSH算法的空間復(fù)雜度相對(duì)于傳統(tǒng)的AND-OR構(gòu)造大幅度降低；第二，C2SLSH算法方案根據(jù)LSH相似度即沖突計(jì)數(shù)排序的方式返回最終結(jié)果集，相對(duì)于傳統(tǒng)AND-OR及其相關(guān)算法而言，能夠保證快速的查詢時(shí)間.

5 C2SLSH的分布式實(shí)現(xiàn)

為滿足對(duì)大數(shù)據(jù)的處理需求，本節(jié)在MapReduce框架上實(shí)現(xiàn)C2SLSH算法來(lái)處理kNN問(wèn)題.首先選取合適的哈希函數(shù)，然后計(jì)算數(shù)據(jù)對(duì)象的哈希值，得到相應(yīng)的哈希索引值，索引文件由分布式系統(tǒng)集群共同維持，索引構(gòu)造的目標(biāo)是快速準(zhǔn)確地處理數(shù)據(jù)對(duì)象的近鄰查詢.查詢時(shí)首先計(jì)算查詢對(duì)象的哈希值，然后在索引中查找與查詢對(duì)象具有相同哈希值的對(duì)象，確定每個(gè)查詢對(duì)象匹配的候選對(duì)象集合，并對(duì)集合中的對(duì)象計(jì)數(shù)并排序，將沖突次數(shù)最多的對(duì)象作為結(jié)果依次輸出.

圖3展示了LSH函數(shù)和MapReduce框架緊密結(jié)合構(gòu)建LSH索引的過(guò)程.建立索引的過(guò)程是一個(gè)MapReduceJob過(guò)程.為減少分布式計(jì)算過(guò)程中的數(shù)據(jù)傳輸量，在數(shù)據(jù)預(yù)處理階段我們?yōu)樗械臄?shù)據(jù)對(duì)象設(shè)置唯一的id號(hào).分布式LSH索引構(gòu)造以及查詢過(guò)程如下.

（1）計(jì)算哈希值：在圖3中Map階段，預(yù)先初始化所選擇的函數(shù)，Map階段使用一致的函數(shù)參數(shù)，Map階段計(jì)算對(duì)象的哈希值，由哈希函數(shù)及其哈希桶形成組合對(duì)Intpair（Intpair是自定義類，可以保存兩個(gè)整型數(shù)值）作為MapReduce過(guò)程中的key，而對(duì)象的id號(hào)作為value，最終Map階段輸出鍵值對(duì)為（（Table，bucket）id）.

（2）索引文件分配：在圖3中Reduce階段，對(duì)相同桶內(nèi)的數(shù)據(jù)進(jìn)行歸并，生成索引文件，由分布式文件系統(tǒng)HDFS維持，每個(gè)哈希桶對(duì)應(yīng)HDFS中的一個(gè)文件.由于將數(shù)據(jù)對(duì)象設(shè)置了id標(biāo)識(shí)，也使得索引文件占用的存儲(chǔ)空間更小，便于調(diào)到內(nèi)存中處理.本階段將具有相同哈希值的ids保存到同一個(gè)二進(jìn)制文件中，索引文件內(nèi)容為鍵值對(duì)（（Table，bucket），id1id2…）.至此，構(gòu)建索引的過(guò)程完成.

kNN查詢過(guò)程，首先使用索引構(gòu)造過(guò)程中所選定的LSH函數(shù)計(jì)算查詢對(duì)象的哈希值，接著根據(jù)哈希值選擇將被統(tǒng)計(jì)計(jì)數(shù)的候選對(duì)象集，沖突計(jì)數(shù)排序的kNN查詢處理過(guò)程使用兩個(gè)MapReduce Job來(lái)完成，最終將為每個(gè)查詢對(duì)象輸出k近鄰結(jié)果集.處理流程如圖4所示.

（3）相關(guān)候選者統(tǒng)計(jì)：在圖4中Map1階段，輸入文件會(huì)被分割成多個(gè)輸入分片，InputFormat類可以直接讀取二進(jìn)制存儲(chǔ)的文件，獲取相應(yīng)的key和value作為輸入.Map1階段為每個(gè)查詢對(duì)象輸出一個(gè)組合對(duì)，當(dāng)輸入分片中的所有候選者被處理完，這時(shí)key是查詢對(duì)象，value是id及它們和查詢對(duì)象的沖突統(tǒng)計(jì)，此階段的輸出為（query，（id，1））.

（4）候選者計(jì)數(shù)：在圖4中Reduce1階段，將Map1階段生成的二元鍵值對(duì)分發(fā)到Reduce1階段，對(duì)產(chǎn)生的結(jié)果進(jìn)行聚合.處理中將（query，（id，1））轉(zhuǎn)變?yōu)椋ǎ╭uery，id），1），此時(shí)key值為（query，id），聚合具有相同key值的對(duì)象集并統(tǒng)計(jì)計(jì)數(shù)，生成（query，id），count））鍵值對(duì)，這里count是查詢對(duì)象和候選對(duì)象的沖突次數(shù)，最終結(jié)果輸出到HDFS上.

（5）候選集結(jié)果排序：接下來(lái)對(duì)第一個(gè)MapReduce Job的輸出結(jié)果按計(jì)數(shù)降序排序.在這個(gè)過(guò)程中，不僅對(duì)key進(jìn)行排序，也要對(duì)相同key的values進(jìn)行排序，所以接下來(lái)我們使用自定義的二次排序方法.在圖4 中Map2階段對(duì)每一個(gè)讀入的（query，（id，count））鍵值對(duì)變換為（query，count）id），然后Shuffle階段進(jìn)行二次排序，排序結(jié)果發(fā)送到Reduce2階段.

（6）返回最后結(jié)果：在圖4中Reduce2階段，對(duì)于kNN查詢，我們?yōu)槊總€(gè)查詢對(duì)象返回前k個(gè)結(jié)果，輸出形式為（query，id）count））.這種處理方式，可以在一個(gè)MapReduce任務(wù)中同時(shí)處理多個(gè)查詢，當(dāng)查詢集較大時(shí)也能夠使用該方法解決kNN問(wèn)題.

6 實(shí)驗(yàn)

6.1實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)在16臺(tái)PC機(jī)組成的集群上進(jìn)行，其中1臺(tái)作為Master節(jié)點(diǎn)，其余15臺(tái)都可以作為Slave節(jié)點(diǎn).每臺(tái)PC配置相同：CPU為Intel Core i3 3.4GHz，8GB內(nèi)存，操作系統(tǒng)為CentOS6.5，Hadoop版本為1.2.1，JDK版本為1.6.采用兩個(gè)真實(shí)數(shù)據(jù)集來(lái)評(píng)估本文的方法，一個(gè)是LabelMe圖像數(shù)據(jù)集［18］，每幅圖像被表示為512維的GIST特征.另一個(gè)是Tiny圖像數(shù)據(jù)集［19］，每幅圖像被表示為384維的GIST特征.這些數(shù)據(jù)集已被用于評(píng)價(jià)其他LSH算法的性能［20］.

6.2實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)對(duì)比算法包括：基本的線性掃描、RankReduce［21］和LSHZ（LSHZ-order）.

在Hadoop平臺(tái)上利用LSH高效處理高維數(shù)據(jù)的kNN查詢，據(jù)我們所知，目前只有 RankReduce算法.它采用“過(guò)濾+驗(yàn)證”過(guò)程，首先從所有數(shù)據(jù)集獲得查詢結(jié)果的候選集，然后在候選集中，計(jì)算與查詢對(duì)象之間的距離并排序，從而獲得最終的結(jié)果集.RankReduce的計(jì)算量較大，尤其是驗(yàn)證過(guò)程.另外，對(duì)于不同的哈希表，不同候選集中可能包含較多相同的對(duì)象，存在重復(fù)計(jì)算，同樣需要較大的計(jì)算量.

另外，我們認(rèn)為，將LSB［22］和H-zkNNJ［23］結(jié)合，也可處理高維數(shù)據(jù)的kNN查詢.對(duì)于高維數(shù)據(jù)集，LSB分兩個(gè)階段處理：首先用LSH降維，然后將降維后數(shù)據(jù)轉(zhuǎn)換成Z-order值，并用B-tree來(lái)索引.但LSB算法是集中式平臺(tái)下的研究成果，不能直接遷移到分布式平臺(tái)上使用.H-zkNNJ是用Z-order解決多維大數(shù)據(jù)kNN連接的方法，但當(dāng)數(shù)據(jù)維度達(dá)到30維以上時(shí)，算法效率會(huì)明顯降低［23］，顯然無(wú)法直接用于高維數(shù)據(jù)處理.我們把結(jié)合算法稱為L(zhǎng)SHZ算法，并實(shí)驗(yàn)比較.

6.2.1準(zhǔn)確率與精確性

評(píng)估準(zhǔn)確性的方法，是將其與線性掃描所有數(shù)據(jù)做對(duì)比，并將線性掃描過(guò)程作為一個(gè)MapReduce Job來(lái)實(shí)現(xiàn).對(duì)于給定k值的kNN搜索算法的性能度量，我們使用C（v）來(lái)代表正確率，線性掃描kNN返回結(jié)果集使用N（v）表示，C（v）就是N（v）在所提算法得到的結(jié)果集I（v）中所占的比例，可以使用下面這個(gè)公式來(lái)表示：

實(shí)驗(yàn)使用數(shù)量為50000的LabelMe數(shù)據(jù)集和Tiny數(shù)據(jù)集，改變哈希函數(shù)的個(gè)數(shù)m，同時(shí)改變桶寬w的大小，來(lái)測(cè)定算法的準(zhǔn)確性.在這兩個(gè)數(shù)據(jù)集上使用相同kNN查詢且令k=10結(jié)果如圖5所示，為提高正確率，在不改變桶寬的情況下，需增加哈希表個(gè)數(shù).固定哈希表的數(shù)目并改變桶寬時(shí)，也可調(diào)整算法的正確率.因此可以選擇適當(dāng)數(shù)目的哈希表和合適的桶寬保證較高的正確率.由于每個(gè)哈希表中都會(huì)創(chuàng)建所有數(shù)據(jù)的副本，因此實(shí)驗(yàn)中需要權(quán)衡存儲(chǔ)成本與執(zhí)行時(shí)間.

LSH是一種隨機(jī)的算法，它并不能保證返回精確最近鄰，但會(huì)高概率得到近似最近鄰，我們采用和文獻(xiàn)［11］相同的測(cè)量方法來(lái)評(píng)估查詢結(jié)果的精確性.特別地，對(duì)于一個(gè)查詢對(duì)象q通過(guò)相應(yīng)算法所得到的kNN查詢結(jié)果為o1，…，ok，并根據(jù)他們與查詢對(duì)象q距離的不減順序排序，使用代表線性掃描所得到的到查詢對(duì)象q的kNN結(jié)果，同樣以距離的不減順序進(jìn)行排序.那么，Rank-i近似指標(biāo)可以定義為Ri（q）=代表歐氏距離，平均精確指標(biāo)被定義為，其中平均精確指標(biāo)是一個(gè)大于1的數(shù)值，其值越接近1，結(jié)果越精確.給定一個(gè)查詢集合Q時(shí)，其中所有查詢對(duì)象的平均精確指標(biāo)作為查詢精確性的最終測(cè)度，這個(gè)平均值被稱為總體平均精確指標(biāo)，如圖6所示.

從圖6中可以看出，在LableMe和Tiny數(shù)據(jù)集上搜索的Rank-i總體平均精確指標(biāo).這里實(shí)驗(yàn)設(shè)置哈希函數(shù)為20個(gè)，桶寬w為400，根據(jù)H-zkNNJ實(shí)驗(yàn)結(jié)果，兩個(gè)偏移量副本就可以達(dá)到較好的效果，我們?cè)谶@里設(shè)置Z-order偏移量副本數(shù)目為2.結(jié)果表明，與線性掃描方法相比，C2SLSH方法、RankReduce方法以及LSHZ方法所返回的結(jié)果對(duì)象的先后順序都有誤差，隨著k值的增大，三種方法的結(jié)果越來(lái)越接近.盡管C2SLSH算法不能返回查詢對(duì)象k個(gè)結(jié)果的精確順序，但能保證查詢結(jié)果的錯(cuò)誤率較小，從而滿足近似最近鄰的查詢需求.

6.2.2運(yùn)行時(shí)間

本實(shí)驗(yàn)評(píng)估C2SLSH算法時(shí)間效率是與兩種分布式下LSH相關(guān)算法做對(duì)比.C2SLSH對(duì)所有查詢對(duì)象的候選結(jié)果集統(tǒng)計(jì)計(jì)數(shù)并排序，根據(jù)沖突次數(shù)獲得最終結(jié)果集I（v），因此有較好的時(shí)間效率.實(shí)驗(yàn)使用四個(gè)節(jié)點(diǎn)的集群，數(shù)量為20000、40000、60000、80000、100000 的LableMe及Tiny數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集，對(duì)比測(cè)量同等實(shí)驗(yàn)條件下三種算法的查詢時(shí)間.實(shí)驗(yàn)結(jié)果如圖7所示，結(jié)果表明相同規(guī)模的數(shù)據(jù)要達(dá)到相同精確率時(shí)，C2SLSH方法更快，約是 RankReduce方法的運(yùn)行時(shí)間的三分之一甚至更少.

另外，為了測(cè)定桶寬w的變化對(duì)C2SLSH算法運(yùn)行時(shí)間的影響，同樣采用四個(gè)節(jié)點(diǎn)集群作為實(shí)驗(yàn)平臺(tái)，固定哈希表數(shù)目為 20，使用數(shù)量為50000的LableMe和Tiny圖像數(shù)據(jù)集.使得桶寬w是一個(gè)連續(xù)變量，對(duì)桶寬大小提供了較小的控制，如圖8所示，在固定哈希表個(gè)數(shù)的情況下，隨著桶寬的變大，雖然可以提高查詢結(jié)果的精確率，但是所需運(yùn)行時(shí)間也會(huì)變長(zhǎng).

6.2.3可擴(kuò)展性

為了測(cè)試C2SLSH算法的可擴(kuò)展性，我們?cè)诓煌?jié)點(diǎn)個(gè)數(shù)的分布式集群上，采用6組不同數(shù)量的圖像數(shù)據(jù)進(jìn)行測(cè)試.實(shí)驗(yàn)集群的節(jié)點(diǎn)個(gè)數(shù)采用遞增的形式（4個(gè)、8個(gè)、16個(gè)）；對(duì)于不同數(shù)據(jù)集LableMe和Tiny的LSH參數(shù)設(shè)置，我們根據(jù)之前的實(shí)驗(yàn)結(jié)果，選定20個(gè)哈希函數(shù)，固定桶寬為400，使用20000、40000、60000、80000、100000的LableMe圖像數(shù)據(jù)集以及Tiny圖像數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比.隨著數(shù)據(jù)量的增長(zhǎng)，查詢運(yùn)行時(shí)間增長(zhǎng)越緩慢則表明分布式索引策略越好.從圖9中可以看到隨著數(shù)據(jù)量的增加，查詢時(shí)間增加相對(duì)緩慢，另外，增加集群節(jié)點(diǎn)個(gè)數(shù)時(shí)，查詢時(shí)間也會(huì)隨之減小，所以C2SLSH適合分布式平臺(tái)，具有較好的穩(wěn)定性和可擴(kuò)展性.

7 總結(jié)

本文為解決高維大數(shù)據(jù)的kNN查詢問(wèn)題提出了一個(gè)基于LSH適合分布式平臺(tái)的高效算法，首先對(duì)這個(gè)算法進(jìn)行了理論分析，然后在Hadoop分布式平臺(tái)上實(shí)現(xiàn)了該算法并測(cè)試了該算法的可行性.通過(guò)實(shí)驗(yàn)，驗(yàn)證了該算法在分布式平臺(tái)上的有效性.C2SLSH算法不僅可以處理高維大規(guī)模數(shù)據(jù)的kNN問(wèn)題，也可以把它擴(kuò)展到其他感興趣的應(yīng)用上，如近似檢測(cè)，文檔分類或者推薦系統(tǒng)等.

［1］Shi J R，et al.Metric learning for high-dimensional tensor Data［J］.Chinese Journal of Electronics，2011，20（3）：495 -498.

［2］鞏敦衛(wèi)，王更星，孫曉燕.高維多目標(biāo)優(yōu)化問(wèn)題融入決策者偏好的集合進(jìn)化優(yōu)化方法［J］.電子學(xué)報(bào)，2014，42 （5）：933-939. GONG Dun-wei，WANG Geng-xing，SUN Xiao-yan.Setbased evolutionary optimization algorithms integrating decision-maker’s preferences for many-objective optimization problems［J］.Acta Electronica Sinica，2014，42（5）：933-939.（in Chinese）

［3］趙永威，郭志剛，李弼程，等.基于隨機(jī)化視覺(jué)詞典組和上下文語(yǔ)義信息的目標(biāo)檢索方法［J］.電子學(xué)報(bào)，2012，40（12）：2472-2480. ZHAO Yong-wei，GUO Zhi-gang，LI Bi-cheng，et al.Object retrieval method based on randomized visual dictionaries and contextual semantic information［J］.Acta Electronica Sinica，2012，40（12）：2472-2480.（in Chinese）

［4］Guttman A.R-trees：A Dynamic Index Structure for Spatial Searching［M］.USA：ACM Press，1984.

［5］Bentley J L.K-d trees for semidynamic point sets［A］.Proceedings of the Sixth Annual Symposium on Computational Geometry［C］.USA：ACM Press，1990.187-197.

［6］Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing［A］.Proceedings of the 25th International Conference on Very Large Data Bases［C］.USA：VLDB Press，1999，Vol 99.518-529.

［7］Indyk P，Motwani R.Approximate nearest neighbors：towards removing the curse of dimensionality［A］.Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing［C］.USA：ACM Press，1998.604-613.

［8］Qian Jiangbo，Zhu Qiang，Chen Huahui.Multi-granularity locality-sensitive bloom filter［J］.IEEE Transactions on Computers，2015，64（12）：3500-3514.

［9］Lv Q，Josephson W，Wang Z，et al.Multi-probe LSH：efficient indexing for high-dimensional similarity search［A］. Proceedings of the 33rd International Conference on Very Large Data Bases［C］.USA：VLDB Endowment Press，2007.950-961.

［10］龍柏，孫廣中，熊焰，陳國(guó)良.一種基于多核機(jī)群架構(gòu)的混合索引結(jié)構(gòu)［J］.電子學(xué)報(bào)，2011，39（2）：275-279. LONG Bai，SUN Guang-zhong，XIONG Yan，CHEN Guo-liang.A hybrid index structure based on multi-core cluster［J］. Acta Electronica Sinica，2011，39（2）：275-279.（in Chinese）

［11］Gan Junhao，et al.Locality-sensitive hashing scheme based on dynamic collision counting［A］.Proceedings of the ACM SIGMOD International Conference on Management of Data［C］.USA：ACM Press，2012.1-12.

［12］Hadoop：Open-source Implementation of mapreduce［OL］. http：//lucene.apache.org/hadoop/.2012.

［13］Koga H，Oguri M，Watanabe T.MIXED-LSH：Reduction of remote accesses in distributed locality-sensitive hashing based on L1-distance［A］.Proceedings of IEEE 26th International Conference on Advanced Information Networking and Applications（AINA）［C］.USA：IEEE Press，2012.175-182.

［14］Bahmani B，Goel A，Shinde R.Efficient distributed locality sensitive hashing［A］.Proceedings of the 21st ACM International Conference on Information and Knowledge Management［C］.USA：ACM Press，2012.2174-2178.

［15］Panigrahy R.Entropy based nearest neighbor search in high dimensions［A］.Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm ［C］.USA：ACM Press，2006.1186-1195.

［16］Datar M，Immorlica N，Indyk P，et al.Locality-sensitive hashing scheme based on p-stable distributions［A］.Proceedings of the Twentieth Annual Symposium on Computational Geometry［C］.USA：ACM Press，2004.253-262.

［17］Rajaraman A，Ullman J D.Mining of Massive Datasets ［M］.England：Cambridge University Press，2011.

［18］LabelMe，the Open Annotation Tool［OL］.http：//labelme.csail.mit.edu.

［19］Python Version of Matlab Code for Accessing the Tiny Image Dataset［OL］.http：//horatio.cs.nyu.edu/mit/tiny/data/index.html.

［20］Pan J，Manocha D.Bi-level locality sensitive hashing for k-nearest neighbor computation［A］.Proceedings of IEEE 28th International Conference on Data Engineering（ICDE）［C］.USA：IEEE Press，2012.378-389.

［21］Stupar A，Michel S，et al.Rankreduce processing k-nearest neighbor queries on top of mapreduce［A］.Proceedings of the 8th Workshop on Large-Scale Distributed Systems for Information Retrieval［C］.USA：ACM Press，2010.13-18.

［22］Tao Y，Yi K，et al.Efficient and accurate nearest neighbor and closest pair search in high-dimensional space［J］. ACM Transactions on Database Systems（TODS），2010，35（3）：20.

［23］Zhang C，Li F，Jestes J.Efficient parallel kNN joins for large data in mapreduce［A］.Proceedings of the 15th International Conference on Extending Database Technology ［C］.USA：ACM Press，2012.38-49.

陳葉芳（通信作者） 女，1973年出生于浙江省安吉縣.寧波大學(xué)講師，主要研究方向?yàn)閿?shù)據(jù)處理和挖掘.

E-mail：chenyefang@nbu.edu.cn

LSH-Based Algorithm for k Nearest Neighbor Search on Big Data

WANG Zhong-wei，CHEN Ye-fang，QIAN Jiang-bo，CHEN Hua-hui

（Faculty of Electrical Engineering and Computer Science，Ningbo University，Ningbo，Zhejiang 315211，China）

The locality sensitive hashing（LSH）and its variants are efficient algorithms to solve the k nearest neighbor（kNN）search problems on high-dimensional data.However，with the increase of large data size，the traditional centralized LSH algorithms cannot meet the challenge of the big data era.Based on a new AND-OR construction，this paper proposes an algorithm（called C2SLSH）for the k nearest neighbor search on big data.Different to the traditional algorithms，the C2SLSH can directly get the results from an index without having to compare the original data.The theoretical analysis and experimental results show that the algorithm has stable scalability on a distributed platform.Furthermore，it is faster than the conventional methods for about three times with the same accuracy rate.

kNN；LSH；MapReduce；collision counting sorting

TP311.13

A

0372-2112（2016）04-0906-07

電子學(xué)報(bào)URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.022

王忠偉 男，1988年出生于河南商丘.寧波大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘.

E-mail：huanfengwei@163.com

2014-12-24；

2015-09-20；責(zé)任編輯：孫瑤

國(guó)家自然科學(xué)基金（No.61472194，No.61572266）；浙江省自然科學(xué)基金（No.LY13F020040）；寧波市自然科學(xué)基金（No. 2014A610023）；“信息與通信工程”浙江省重中之重學(xué)科開(kāi)放基金