多維數(shù)據(jù)近似檢索的分層LSH索引算法模型研究

房華蓉

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 分層LSH索引算法模型

3.1 分層LSH算法流程

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

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

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

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

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

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

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

4 小結(jié)

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

參考文獻(xiàn)：

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

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

[3] 孟小峰，慈祥. 大數(shù)據(jù)管理：概念、技術(shù)與挑戰(zhàn)[J]. 計(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] 謝鯤， 秦拯， 文吉?jiǎng)偅?等. 聯(lián)合多維布魯姆過(guò)濾器查詢算法[J]. 通信學(xué)報(bào)，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