房華蓉

摘要：該文鑒于數(shù)據(jù)管理技術(shù)發(fā)展的前瞻性考慮，以多維數(shù)據(jù)為處理對象，探索高性能數(shù)據(jù)過濾器的若干理論和實現(xiàn)技術(shù)，針對假陽性和假陰性過高的問題，以及對時空效率的要求，設(shè)計了適合多維數(shù)據(jù)近似檢索的分層LSH索引算法模型。

關(guān)鍵詞：多維數(shù)據(jù)；布魯姆過濾器；局部敏感哈希；分層局部敏感哈希索引

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）02-0213-03

隨著互聯(lián)網(wǎng)、電子商務(wù)等信息技術(shù)的高速發(fā)展，數(shù)據(jù)規(guī)模呈海量增長，多個領(lǐng)域已經(jīng)或正在積累TB、PB甚至EB級的大數(shù)據(jù)[1，2]。如沃爾瑪超市數(shù)據(jù)庫超過2.5PB，每小時需要處理100余萬條用戶請求；社交網(wǎng)絡(luò)Facebook存儲了超過500億張的照片；互聯(lián)網(wǎng)數(shù)據(jù)資源每兩年翻一番；全球的工業(yè)設(shè)備、汽車、電表上有無數(shù)的傳感器，隨時產(chǎn)生多種多樣的海量數(shù)據(jù)信息。這些都標(biāo)志著大數(shù)據(jù)時代已經(jīng)來到，學(xué)術(shù)界、工業(yè)界和政府都已經(jīng)開始密切關(guān)注大數(shù)據(jù)及其檢索問題。

2012年美國奧巴馬政府發(fā)布了“Big Data Research and DevelopmentInitiative”[3]，投資2億以上美元，計劃在科學(xué)研究、環(huán)境、生物醫(yī)學(xué)等領(lǐng)域利用大數(shù)據(jù)技術(shù)進(jìn)行突破性研究，將“大數(shù)據(jù)戰(zhàn)略”上升為國家戰(zhàn)略。我國政府多部規(guī)劃和項目指南都對“大數(shù)據(jù)”相關(guān)技術(shù)密切關(guān)注：《國家中長期科技發(fā)展規(guī)劃綱要（2006-2020年）》提出“重點(diǎn)研究……海量信息處理及知識挖掘的理論與方法”；2014國家自然科學(xué)基金優(yōu)先資助重點(diǎn)領(lǐng)域包括“大數(shù)據(jù)技術(shù)和應(yīng)用中的挑戰(zhàn)性科學(xué)問題”，并列出10個研究方向。

1 多維數(shù)據(jù)及其檢索策略

信息存儲空間的多元化給網(wǎng)絡(luò)中數(shù)據(jù)資源的存儲管理及新資源開發(fā)帶來了新的挑戰(zhàn)。大數(shù)據(jù)的存儲與表示，大數(shù)據(jù)中知識快速且高效的挖掘是目前各互聯(lián)網(wǎng)服務(wù)供應(yīng)商關(guān)注的熱點(diǎn)，普通網(wǎng)絡(luò)用戶也希望通過大數(shù)據(jù)獲得更多的增值服務(wù)。數(shù)據(jù)量及數(shù)據(jù)復(fù)雜度急劇增長時，知識發(fā)現(xiàn)的難度及大大增加，計算量和響應(yīng)時間也隨之變化。研究與之對應(yīng)的高效查詢算法查找定位信息資源已經(jīng)成為現(xiàn)代網(wǎng)絡(luò)發(fā)展分布式信息共享中最常見的問題。精簡結(jié)構(gòu)的查詢算法已經(jīng)成為提升網(wǎng)絡(luò)軟件體系結(jié)構(gòu)和完成大規(guī)模高效數(shù)據(jù)管理的關(guān)鍵。

由于大數(shù)據(jù)的數(shù)據(jù)體量巨大、類型繁多、價值大但有效信息比例低、要求處理速度快的特點(diǎn)，對當(dāng)代信息傳輸、計算、存儲以及面向各種應(yīng)用的數(shù)據(jù)處理技術(shù)提出了前所未有的挑戰(zhàn)。針對這些特征，學(xué)術(shù)界公認(rèn)的大數(shù)據(jù)處理策略是先用過濾器快速過濾掉大部分無用的數(shù)據(jù)，留下可能有用的數(shù)據(jù)做進(jìn)一步處理。但是，如何從靜態(tài)或動態(tài)的海量數(shù)據(jù)中“提純”出有價值的數(shù)據(jù)面臨諸多困難，如：1）大數(shù)據(jù)時代的算法由于實時性的特點(diǎn)，其準(zhǔn)確率不再是最主要指標(biāo)，很多算法需要在實時性和準(zhǔn)確率之間取得平衡；2）數(shù)據(jù)過濾必須更加謹(jǐn)慎，如果粒度過細(xì)，很容易將有用的信息過濾掉；如果過粗，又無法達(dá)到真正的清洗效果，因此需要在質(zhì)和量之間仔細(xì)考慮和權(quán)衡。

大數(shù)據(jù)檢索的實際應(yīng)用中多采用近似查詢，一般而言與目標(biāo)距離越近，數(shù)據(jù)的價值就越高。為提高速度，可以設(shè)置一個多維數(shù)據(jù)過濾器，根據(jù)距離過濾掉大部分查詢數(shù)據(jù)，少量剩下的數(shù)據(jù)可以再通過常規(guī)方法進(jìn)一步處理，可以顯著提高系統(tǒng)的整體性能。這個過濾器完成的就是近似成員查詢（ApproximateMembership Query，AMQ），即回答“查詢對象q是否接近于數(shù)據(jù)集合中的某個對象”?，F(xiàn)有AMQ技術(shù)主要是結(jié)合局部敏感哈希（Locality Sensitive Hashing，LSH）和布魯姆過濾器（Bloom Filter，BF）設(shè)計的，如DSBF和LSBF。不過布魯姆過濾器存在假陽性錯誤，局部敏感哈希算法需要大量的哈希表來建立索引結(jié)構(gòu)，這就導(dǎo)致了大量的內(nèi)存消耗，查詢時也會帶來大量的I/O訪問。此外，盡管LSH的查詢時間效率已經(jīng)比較高了，但是依然存在進(jìn)一步優(yōu)化的空間。典型DSBF和LSBF這兩個技術(shù)都有一個限制，即它們僅能過濾給定距離的AMQ查詢。因此研究BF和LSH算法的特性，針對BF及LSH的缺點(diǎn)提出改進(jìn)方案或者提出性能更優(yōu)的相似性檢索算法具有重要的研究意義。為了提出性能及適應(yīng)性更好的相似性檢索算法，以優(yōu)化LSH結(jié)構(gòu)、提升AMQ的質(zhì)量和效率：設(shè)計多維數(shù)據(jù)近似檢索的分層LSH索引算法模型。

2 基于BF及LSH的不同維度數(shù)據(jù)檢索技術(shù)

布魯姆過濾器（Bloom Filter，BF）是由B.H.Bloom在1970提出的經(jīng)典過濾器[4]，被廣泛用在網(wǎng)絡(luò)服務(wù)、數(shù)據(jù)包內(nèi)容檢測、信息檢索、分布式數(shù)據(jù)庫、協(xié)作緩存等領(lǐng)域。它對集合采用一個位串表示并能有效支持元素的哈希查找，對每個元素的表示只需要幾個比特，是一種能夠表示集合、支持集合查詢的簡潔數(shù)據(jù)結(jié)構(gòu)，能夠有效地過濾掉不屬于集合的元素。布魯姆過濾器結(jié)構(gòu)的實質(zhì)是將集合中的元素通過n個哈希函數(shù)映射到位串向量中，與傳統(tǒng)的哈希查詢算法中哈希存儲表不同，布魯姆過濾器中哈希表退化為一個位串，一個元素僅占用幾個比特位。進(jìn)行元素查詢時，計算n個哈希函數(shù)，判斷這個位串向量的n個對應(yīng)比特位是否都為1。不過，布魯姆過濾器作為一種集合查詢的數(shù)據(jù)結(jié)構(gòu)，在達(dá)到其高效簡潔表示集合的同時，卻存在可控的假陽性誤判。

LSH技術(shù)是由P.Indyk等在1998年提出，它的思想是：先對數(shù)據(jù)集中的點(diǎn)進(jìn)行哈希函數(shù)的映射，這樣近距離點(diǎn)的沖突概率提高而遠(yuǎn)距離點(diǎn)的沖突概率降低。在查詢時，將查詢點(diǎn)按照相同的哈希函數(shù)哈希到桶中，然后取出桶中的所有點(diǎn)作為候選近似最近鄰點(diǎn)，最后計算查詢點(diǎn)與每個候選近似最近鄰點(diǎn)的距離，通過該距離判斷是否符合查詢條件。使用哈希函數(shù)對整個數(shù)據(jù)集進(jìn)行過濾，得到可能滿足查詢條件的點(diǎn)再計算距離，就避免點(diǎn)與數(shù)據(jù)集中所有點(diǎn)進(jìn)行距離計算，提高了查詢效率且無需降維。

2.1 單維數(shù)據(jù)布魯姆過濾器

針對不同應(yīng)用，布魯姆過濾器有很多改進(jìn)。計數(shù)布魯姆過濾器CBF[5]將1位的比特擴(kuò)展為3位或4位的計數(shù)器，能夠處理元素刪除操作。CBF可以正確地刪除已經(jīng)在集合中的元素，但如果這一先決條件不滿足，就會產(chǎn)生假陰性（false negative）問題。為解決此問題，Guo等人[6]提出了一種新方案，在不減少0比特的情況下增加1比特，使得假陰性和假陽性一樣減少。Time Decaying BF[7]在遞減計數(shù)器值的同時也考慮時間因素。SBF[8]是另一個重復(fù)元素檢測的解決方案，在SBF中0的預(yù)期分位數(shù)保持恒定，使得它適合在數(shù)據(jù)流中的重復(fù)檢測，它還降低了假陽性和假陰性率。Space-code BF[9]關(guān)注測量精度、計算及存儲復(fù)雜性之間的權(quán)衡。與標(biāo)準(zhǔn)的BF需要k次訪問內(nèi)存不同，Qiao等[10]提出Bloom-1只需要訪問一次內(nèi)存，他們還分析了不同的數(shù)據(jù)結(jié)構(gòu)和性能，以獲得查詢代價和假陽性率都可接受的折中方案。endprint

2.2 低維數(shù)據(jù)布魯姆過濾器

以上這些研究針對的是單維數(shù)據(jù)，而實際應(yīng)用中，很多數(shù)據(jù)都是多維的。但目前多維布魯姆過濾器研究還比較少，且主要集中在數(shù)據(jù)的集合判斷問題。Guo等[11]提出了多維動態(tài)布魯姆的過濾器（MDDBF）來判斷多維數(shù)據(jù)是否屬于一個集合，基本的想法是對于s維的集合，設(shè)置s個標(biāo)準(zhǔn)BF 過濾器。由于MDDBF方法失去了屬性間的關(guān)聯(lián)信息，將增加誤報的概率。Xiao等[12]意識到這個問題，提出輔助結(jié)構(gòu)捕捉所有屬性的內(nèi)在相關(guān)性。與MDDBF相比，能夠處理多個屬性，可以提供更快的查詢服務(wù)，出現(xiàn)假陽性的概率要低得多，也節(jié)省了存儲空間。聯(lián)合多維布魯姆過濾器（CMDBF）[13]新增一個用于表示數(shù)據(jù)整體的聯(lián)合布魯姆過濾器CBF，CMDBF中數(shù)據(jù)表示和查找分兩步進(jìn)行，即將MDBF的各屬性的表示和查詢作為第一步，第二步聯(lián)合數(shù)據(jù)所有屬性域，利用CBF完成數(shù)據(jù)整體的表示和查詢確認(rèn)。

以上這些多維布魯姆過濾器的更新離不開原始數(shù)據(jù)，即將原始數(shù)據(jù)的各個維通過哈希運(yùn)算后才能更新多維過濾器。但在實際應(yīng)用中，為節(jié)省空間，一般只保留概要數(shù)據(jù)（即布魯姆過濾器），于是無法根據(jù)某一屬性刪除的原始數(shù)據(jù)來更新過濾器。

2.3 多維數(shù)據(jù)的近似查詢-LSH和BF的優(yōu)化組合

傳統(tǒng)算法中基于空間劃分的樹形檢索算法，如各類樹型算法，在檢索對象低維度、低數(shù)據(jù)量的前提下，加速效果明顯。隨著數(shù)據(jù)維度的增加和數(shù)據(jù)量的加大，這些算法的加速效果明顯降低。所以，面對高維度的海量數(shù)據(jù)，這些樹形檢索算法速度上的改進(jìn)微乎其微，甚至還比不上暴力檢索或者線性檢索的速度。

目標(biāo)函數(shù)中近鄰關(guān)系確定是解決最近鄰檢索的速度瓶頸問題，有人提出近似的思想，把如果目標(biāo)函數(shù)中的近近鄰關(guān)系定為似最近鄰，如此更改的原因是在多數(shù)情況下，近似最近鄰的結(jié)果和最近鄰是一致的，而且在大多數(shù)的應(yīng)用場合下，近似最近鄰?fù)瑯右部梢詽M足實際的需求。近似最近鄰的概念最早是由Indyk和Motwani提出的[14]，近似最近鄰的檢索時間及數(shù)據(jù)容量成亞線性關(guān)系得到證明，他們舍棄釆用以往的基于空間劃分的方法，比如樹形分割法，提出了一種新的基于哈希索引的思想實現(xiàn)近似最近鄰檢索，即局域敏感哈希（LSH）。此算法的核心思想是設(shè)計幾個哈希函數(shù)來映射數(shù)據(jù)點(diǎn)，每個哈希函數(shù)要能保證距離近的點(diǎn)被映射到同一個桶的概率（又叫碰撞概率）比距離遠(yuǎn)的點(diǎn)被映射到同一個桶的概率大得多；查詢時，使用對應(yīng)的哈希函數(shù)可以把詢問點(diǎn)也映射到對應(yīng)的桶中，檢索到的桶中的點(diǎn)即為近鄰點(diǎn)?；谶@種映射思想，他們在漢明空間（{0，l}d）中提出了一種局域敏感哈希函數(shù)，跟以往的樹形結(jié)構(gòu)算法相比，他們用實驗驗證了這種算法的快速性。2004年，斯坦福大學(xué)的Indy等提出了基于P穩(wěn)態(tài)分布的局域敏感哈希，成功地用在了原始的非漢明空間，即P范數(shù)空間。

LSH是一種近似的近鄰檢索算法，最近鄰數(shù)據(jù)點(diǎn)的檢索概率很高，但也不是絕對準(zhǔn)確，有人通過使用多個哈希函數(shù)構(gòu)建多個哈希表來提高檢索的準(zhǔn)確率，這樣做的問題是存儲空間浪費(fèi)太大。為了解決這個問題， multi-probe LSH[15]連續(xù)探測多個可能包含查詢對象的桶，而不是只探測一個桶，以提高空間和時間效率。Collision Counting LSH（C2LSH）[16]采用了多個LSH函數(shù)構(gòu)造動態(tài)復(fù)合哈希函數(shù)，并設(shè)定碰撞閾值來提高精確度。BayesLSH[17]能迅速剪枝大多數(shù)的假陽性候選對象，顯著提高處理的速度。

這些查詢都具有多維、實時、且多數(shù)查詢都不命中等三個特征。為提高速度，可以設(shè)置一個多維數(shù)據(jù)過濾器，根據(jù)距離過濾掉大部分查詢數(shù)據(jù)，少量剩下的數(shù)據(jù)可以再通過常規(guī)方法進(jìn)一步處理，可以顯著提高系統(tǒng)的整體性能。這個過濾器完成的就是近似成員查詢AMQ，即回答“查詢對象q是否接近于數(shù)據(jù)集合中的某個對象”?，F(xiàn)有AMQ過濾器主要是結(jié)合LSH和Bloom filter 設(shè)計的，如DSBF和LSBF。如今，LSH技術(shù)及其變種是高維空間檢索最先進(jìn)的索引技術(shù)之一。

DSBF首次綜合LSH和BF來過濾AMQ查詢，返回組成員的近似查詢結(jié)果。它可以改善網(wǎng)絡(luò)和數(shù)據(jù)庫應(yīng)用的速度和空間，從而避免很多代價昂貴的比較操作，如最近鄰查詢等。LSBF使用LSH 函數(shù)來構(gòu)造BF過濾AMQ查詢，LSBF還采用了額外的位向量來降低假陽性率。DSBF和LSBF這兩個技術(shù)都有一個限制，即他們僅能過濾給定距離的AMQ 查詢。然而，給定一個合適的距離并不容易，過大或過小的距離值，可能會導(dǎo)致不可接受的查詢結(jié)果。一旦距離值被確定，就不能改變，除非根據(jù)原始數(shù)據(jù)重新構(gòu)造過濾器。然而，為節(jié)省空間，原始數(shù)據(jù)一般并不保存。另外，這兩種過濾器也占用較多的空間開銷，錯誤率相對較大。

2.4 已有技術(shù)的不足

從上面分析可知：（1）單維數(shù)據(jù)過濾器的研究和應(yīng)用相對比較充分；（2）低維數(shù)據(jù)過濾器的研究局限在判斷數(shù)據(jù)是否在集合中，在沒有原始數(shù)據(jù)支持下，無法根據(jù)某一屬性刪除數(shù)據(jù)的布魯姆過濾器更新其余維度的過濾器（項目組成員在這個問題方面已經(jīng)實現(xiàn)了2維數(shù)據(jù)的關(guān)聯(lián)刪除技術(shù)的研究，并已投稿國際頂級會議被錄用）；（3）多維數(shù)據(jù)過濾器的過濾距離固定，無法支持多粒度的過濾距離；（4）多維數(shù)據(jù)的近似查詢中LSH索引表建立時，耗費(fèi)過多內(nèi)存資源；查詢時，頻繁進(jìn)行I/O操作，耗費(fèi)過多的計算時間。

3 分層LSH索引算法模型

3.1 分層LSH算法流程

針對已有的結(jié)合BF和LSH在近似近鄰檢索算法，由于內(nèi)存消耗過大和時空效率不高（頻繁進(jìn)行I/O處理）問題，提出了分層LSH索引算法流程如下：

1） 索引建立：首先對原始多維數(shù)據(jù)利用已有基于p穩(wěn)定分布的哈希函數(shù)族G（多維哈希）進(jìn)行局部敏感哈希到多個哈希表中，對每個數(shù)據(jù)在多哈希表散列的桶號進(jìn)行編碼，形成桶編號；然后對桶編號進(jìn)行一維哈希散列到一維向量（BF）中，相鄰數(shù)據(jù)點(diǎn)有著相近的桶編號，那么相近的桶編號散列到一維向量中也是相近位；再對一維向量中存放的桶編號散列的位進(jìn)行地址合并，完成索引建立。endprint

2） 查詢處理：查詢時，首先對查詢點(diǎn)做多維哈希函數(shù)族的局部敏感哈希到多個桶，將這些桶中的數(shù)據(jù)作為其候選近鄰數(shù)據(jù)點(diǎn)（這樣可以避免假陽性偏高問題，如果相應(yīng)桶中數(shù)據(jù)個數(shù)已達(dá)查詢結(jié)果要求，則結(jié)束）；如果沒有查找到足夠的候選近鄰則繼續(xù)對桶編號散列到BF中位的近鄰進(jìn)行查詢（這樣可以避免假陰性偏高問題），直至查到查詢目標(biāo)。

3.2 分層LSH索引算法模型設(shè)計

結(jié)合傳統(tǒng)LSH在近似近鄰檢索算法中，由于內(nèi)存消耗過大、時空效率不高和假陽性、假陰性過多問題，我們提出了分層LSH索引算法流程，如圖1所示。

分層LSH索引構(gòu)建流程：對多維的原始數(shù)據(jù)進(jìn)行多哈希函數(shù)的局部敏感哈希，先建立一個哈希表，每個哈希表對應(yīng)哈希函數(shù)族G中隨機(jī)選出[l]個g函數(shù)[g1，g2，...，gl]中的一個g函數(shù)，這個方法能大大提高近鄰點(diǎn)的碰撞概率。而每個數(shù)據(jù)點(diǎn)散列到[l]個哈希表的不同桶中，對這些桶號進(jìn)行編碼形成查詢數(shù)據(jù)的哈希桶編號，然后對這些哈希桶編號再進(jìn)行一次一維哈希函數(shù)的散列，將散列地址映射到BF的有關(guān)位中。設(shè)計過程中，考慮到多維數(shù)據(jù)的近似性，近似數(shù)據(jù)的桶編號經(jīng)過一維哈希函數(shù)的散列后的地址在BF中具有高概率的相鄰性，因此可以考慮對BF的這些相鄰位進(jìn)行合并，完成索引的優(yōu)化。

分層LSH中數(shù)據(jù)的查找流程：查找數(shù)據(jù)時首先對查詢點(diǎn)進(jìn)行哈希函數(shù)族的局部敏感哈希，將其映射到各哈希表的不同桶中形成其散列桶的桶編號，然后將這個桶編號對應(yīng)的桶中數(shù)據(jù)作為候選近似查詢目標(biāo)，如果目標(biāo)的數(shù)目達(dá)到了預(yù)期的查詢數(shù)，就鎖定這些數(shù)據(jù)作為候選查詢點(diǎn)；如果沒有達(dá)到，那么在查詢點(diǎn)所對應(yīng)的哈希桶編號再散列的BF位的相鄰位所對的哈希桶編號的數(shù)據(jù)點(diǎn)也作為候選近鄰成員。

4 小結(jié)

本文針對已有的結(jié)合BF和LSH在近似近鄰檢索算法進(jìn)行了總結(jié)，基于已有技術(shù)的內(nèi)存消耗過大和時空效率不高（頻繁進(jìn)行I/O處理）問題，提出了分層LSH索引算法設(shè)計分層LSH索引算法模型，既能避免假陽性和假陰性過高的問題，也能提升算法的時空效率。

參考文獻(xiàn)：

[1] 王珊，王會舉，覃雄派，等. 架構(gòu)大數(shù)據(jù)：挑戰(zhàn)、現(xiàn)狀與展望[J]. 計算機(jī)學(xué)報，2011， 34（10）：1741-1752.

[2] 李建中，劉顯敏. 大數(shù)據(jù)的一個重要方面：數(shù)據(jù)可用性[J]. 計算機(jī)研究與發(fā)展，2013， 50（06）：1147-1162.

[3] 孟小峰，慈祥. 大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)[J]. 計算機(jī)研究與發(fā)展，2013，50（01）：146-169.

[4] B.H.Bloom. Space/Time Trade-Offs in Hash Coding with Allowable Errors. Comm. ACM， 1970， 13（7）：422-426.

[5] L.Fan， P. Cao， J. Almeida， and A. Z. Broder. Summary Cache： A Scalable Wide-Area Web Cache Sharing Protocol.IEEE/ACM Trans. Networking.2000，8（3）：281-293.

[6] D.Guo， Y. Liu， X. Li， P. Yang.False Negative Problem of Counting Bloom Filter. IEEE Trans.Knowl.Data Eng.2010， 22（5）：651-664.

[7] K.Cheng，L.Xiang， M.Iwaihara， H.Xu， and M.M.Mohania. Timedecaying Bloom filters for Data Streams with Skewed Distributions. in Proc. 15th International Workshop on Research Issues in Data Engineering： Stream Data Mining and Applications. Washington， DC， USA： IEEE Computer Society，2005： 63-69.

[8] F.Deng and D. Rafiei. Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters. in Proc. 2006 ACM SIGMOD International Conference on Management of Data.New York， NY，USA： ACM， 2006： 25-36.

[9] A.Kumar，J.Xu，J.Wang，O.Spatschek， and L.Li.Space-code Bloom Filter for Efficient Per-flow Traffic Measurement. In Proc. IEEE INFOCOM.Hongkong， China， 2004（3）：1762-1773.

[10] Y.Qiao， T.Li， S.Chen.Fast Bloom Filters and Their Generalization.IEEE Transactions on Parallel and Distributed Systems. 2014， 25（1）：93-103.

[11] D.Guo，J. Wu， H.Chen， and X. Luo. Theory and Network Application of Dynamic Bloom Filters.Proc.IEEE INFOCOM， 2006.

[12] B. XIAO， Y HUA. Using Parallel Bloom Filters for Multiattribute Representation on Network Services.IEEE Trans on Parallel and Distributed Systems， 2010， 21（1）：20-32.

[13] 謝鯤， 秦拯， 文吉剛， 等. 聯(lián)合多維布魯姆過濾器查詢算法[J]. 通信學(xué)報，2008， 29 （1）：56-64.

[14] Indyk Piotr，andMotwani Rajeev， Approximate nearest neighbors： towards removing the curse of dimensionality. In the thirtieth Annual ACM Symposium on Theory of Computing，1998，pp.604-613.

[15] Q.Lv，W.Josephson， and Z. Wang. Multi-Probe LSH： Efficient Indexing for High-Dimensional Similarity Search. In VLDB， pages 950-961， 2007.

[16] J.Gan，J.Feng， and Q. Fang. Locality-sensitive Hashing Scheme Based on Dynamic Collision Counting.In SIGMOD， pages 541-552， 2012.

[17] V.Satuluri， and S. Parthasarathy. Bayesian Locality Sensitive Hashing for Fast Similarity Search. In VLDB， pages 430-441， 2012.endprint