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

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

（寧波大學(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)，提出通過索引而不比較原始數(shù)據(jù)直接實(shí)現(xiàn)高維大數(shù)據(jù)k近鄰搜索算法C2SLSH.理論分析和實(shí)驗(yàn)證明，C2SLSH在分布式平臺下具有穩(wěn)定的可擴(kuò)展性，在保證同等精確率的情況下，處理速度大約是現(xiàn)有方法的3倍.

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

1 引言

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

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

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

2 相關(guān)工作

大數(shù)據(jù)處理面臨的一大挑戰(zhàn)是如何設(shè)計(jì)合適的索引結(jié)構(gòu)，從而能高效地完成近鄰搜索.雖然LSH是一種非常流行的高維數(shù)據(jù)處理算法，但是由于其對空間的依賴性較強(qiáng)，因此并不適合直接用來處理大數(shù)據(jù).有研究者改進(jìn)了LSH算法并在分布式平臺上應(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è)簡便方法是每個(gè)節(jié)點(diǎn)都保持相同的哈希表的數(shù)量.但是這會(huì)增加遠(yuǎn)程訪問，因?yàn)樵S多節(jié)點(diǎn)要存取訪問所有的哈希表.如果通信延遲是瓶頸的話，這種方法響應(yīng)時(shí)間會(huì)比較長.MIXED-LSH巧妙地使用為節(jié)點(diǎn)分配哈希桶的方法來減少遠(yuǎn)程訪問.特別地，MIXED-LSH把相關(guān)的哈希桶存儲在一起，分配到同一節(jié)點(diǎn)的哈希桶來自于不同的哈希表.由于這一策略的使用，在處理一個(gè)查詢訪問時(shí)，對于那些應(yīng)該被訪問的對象，執(zhí)行MIXED-LSH索引方法可以一次訪問多個(gè)哈希桶，從而減少了遠(yuǎn)程訪問的頻率.MIXED-LSH重點(diǎn)在于解決分布式環(huán)境下所產(chǎn)生的網(wǎng)絡(luò)開銷，其使用的距離度量是L1距離，很難有效的擴(kuò)展到其他距離度量的應(yīng)用.另外MapReduce和P2P是不同的分布式環(huán)境，不能遷移應(yīng)用.

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

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

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

定義1（LSH） 設(shè)S是距離度量dist的（數(shù)據(jù)）對象集合，d1、d2為距離度量dist的兩個(gè)距離.如果哈希函數(shù)族H中的每一個(gè)函數(shù)h滿足如下兩個(gè)條件，則哈希函數(shù)族H對于S中任意對象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］.在這種情況下，對每一個(gè)高維數(shù)據(jù)對象v，哈希函數(shù)形式為

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

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

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

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

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

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

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

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

C2SLSH對固定個(gè)數(shù)的哈希函數(shù)的結(jié)果進(jìn)行沖突次數(shù)統(tǒng)計(jì)并排序，間接實(shí)現(xiàn)了更高效的 α-AND構(gòu)造和β-OR構(gòu)造.也就是說，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è)，再改變α的取值，每次減小1，一直找到k個(gè)結(jié)果并返回.根據(jù)定理1，對于C2SLSH算法的AND-OR方案，令u=p（σ）代表相似對象在一個(gè)哈希表中沖突的概率，假設(shè)這個(gè)過程中α的值改變了γ次，根據(jù)α和γ的取值，可以得出相似對象沖突的概率

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)在16臺PC機(jī)組成的集群上進(jìn)行，其中1臺作為Master節(jié)點(diǎn)，其余15臺都可以作為Slave節(jié)點(diǎn).每臺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ù)集來評估本文的方法，一個(gè)是LabelMe圖像數(shù)據(jù)集［18］，每幅圖像被表示為512維的GIST特征.另一個(gè)是Tiny圖像數(shù)據(jù)集［19］，每幅圖像被表示為384維的GIST特征.這些數(shù)據(jù)集已被用于評價(jià)其他LSH算法的性能［20］.

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

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

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

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

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

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

實(shí)驗(yàn)使用數(shù)量為50000的LabelMe數(shù)據(jù)集和Tiny數(shù)據(jù)集，改變哈希函數(shù)的個(gè)數(shù)m，同時(shí)改變桶寬w的大小，來測定算法的準(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)衡存儲成本與執(zhí)行時(shí)間.

LSH是一種隨機(jī)的算法，它并不能保證返回精確最近鄰，但會(huì)高概率得到近似最近鄰，我們采用和文獻(xiàn)［11］相同的測量方法來評估查詢結(jié)果的精確性.特別地，對于一個(gè)查詢對象q通過相應(yīng)算法所得到的kNN查詢結(jié)果為o1，…，ok，并根據(jù)他們與查詢對象q距離的不減順序排序，使用代表線性掃描所得到的到查詢對象q的kNN結(jié)果，同樣以距離的不減順序進(jìn)行排序.那么，Rank-i近似指標(biāo)可以定義為Ri（q）=代表歐氏距離，平均精確指標(biāo)被定義為，其中平均精確指標(biāo)是一個(gè)大于1的數(shù)值，其值越接近1，結(jié)果越精確.給定一個(gè)查詢集合Q時(shí)，其中所有查詢對象的平均精確指標(biāo)作為查詢精確性的最終測度，這個(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á)到較好的效果，我們在這里設(shè)置Z-order偏移量副本數(shù)目為2.結(jié)果表明，與線性掃描方法相比，C2SLSH方法、RankReduce方法以及LSHZ方法所返回的結(jié)果對象的先后順序都有誤差，隨著k值的增大，三種方法的結(jié)果越來越接近.盡管C2SLSH算法不能返回查詢對象k個(gè)結(jié)果的精確順序，但能保證查詢結(jié)果的錯(cuò)誤率較小，從而滿足近似最近鄰的查詢需求.

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

本實(shí)驗(yàn)評估C2SLSH算法時(shí)間效率是與兩種分布式下LSH相關(guān)算法做對比.C2SLSH對所有查詢對象的候選結(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ù)集，對比測量同等實(shí)驗(yàn)條件下三種算法的查詢時(shí)間.實(shí)驗(yàn)結(jié)果如圖7所示，結(jié)果表明相同規(guī)模的數(shù)據(jù)要達(dá)到相同精確率時(shí)，C2SLSH方法更快，約是 RankReduce方法的運(yùn)行時(shí)間的三分之一甚至更少.

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

6.2.3可擴(kuò)展性

為了測試C2SLSH算法的可擴(kuò)展性，我們在不同節(jié)點(diǎn)個(gè)數(shù)的分布式集群上，采用6組不同數(shù)量的圖像數(shù)據(jù)進(jìn)行測試.實(shí)驗(yàn)集群的節(jié)點(diǎn)個(gè)數(shù)采用遞增的形式（4個(gè)、8個(gè)、16個(gè)）；對于不同數(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)對比.隨著數(shù)據(jù)量的增長，查詢運(yùn)行時(shí)間增長越緩慢則表明分布式索引策略越好.從圖9中可以看到隨著數(shù)據(jù)量的增加，查詢時(shí)間增加相對緩慢，另外，增加集群節(jié)點(diǎn)個(gè)數(shù)時(shí)，查詢時(shí)間也會(huì)隨之減小，所以C2SLSH適合分布式平臺，具有較好的穩(wěn)定性和可擴(kuò)展性.

7 總結(jié)

本文為解決高維大數(shù)據(jù)的kNN查詢問題提出了一個(gè)基于LSH適合分布式平臺的高效算法，首先對這個(gè)算法進(jìn)行了理論分析，然后在Hadoop分布式平臺上實(shí)現(xiàn)了該算法并測試了該算法的可行性.通過實(shí)驗(yàn)，驗(yàn)證了該算法在分布式平臺上的有效性.C2SLSH算法不僅可以處理高維大規(guī)模數(shù)據(jù)的kNN問題，也可以把它擴(kuò)展到其他感興趣的應(yīng)用上，如近似檢測，文檔分類或者推薦系統(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)化問題融入決策者偏好的集合進(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ī)化視覺詞典組和上下文語義信息的目標(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］龍柏，孫廣中，熊焰，陳國良.一種基于多核機(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é)任編輯：孫瑤

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