劉根平

（寧波大學(xué)，浙江 寧波 315211）

集中式環(huán)境下的局部敏感哈希算法綜述*

劉根平

（寧波大學(xué)，浙江 寧波 315211）

局部敏感哈希算法是一種很流行的高維相似性查找算法。通過(guò)總結(jié)多篇已發(fā)表論文，介紹了集中式環(huán)境下的局部敏感哈希算法及其實(shí)現(xiàn)，分析了各種局部敏感哈希算法的特點(diǎn)和優(yōu)缺點(diǎn)。在近似最近鄰查詢(xún)中的廣泛應(yīng)用證實(shí)了局部敏感哈希算法的有效性。

高維數(shù)據(jù) 相似性搜索 KNN查詢(xún) 局部敏感哈希算法

1 引言

近年來(lái)，隨著互聯(lián)網(wǎng)的快速發(fā)展，產(chǎn)生的數(shù)據(jù)數(shù)以萬(wàn)計(jì)。如何從龐大的數(shù)據(jù)中挖掘出有用的信息，顯得尤為重要，如在圖像數(shù)據(jù)庫(kù)中尋找內(nèi)容相似或者語(yǔ)意相關(guān)的圖像。相似性查詢(xún)算法的研究成為眾多研究者研究的內(nèi)容，是一個(gè)很有意義的研究方向。

在解決最近鄰查詢(xún)問(wèn)題中，經(jīng)常用到的方法有傳統(tǒng)的基于樹(shù)（如k-d tree等）的空間劃分算法。這些傳統(tǒng)的方法在數(shù)據(jù)維度較低時(shí)性能良好，然而在維度超過(guò)10以后，算法的性能會(huì)迅速下降，有時(shí)甚至不如暴力算法。為解決高維數(shù)據(jù)問(wèn)題，有人提出可以使用精度來(lái)?yè)Q效率。這樣把求最近鄰問(wèn)題轉(zhuǎn)化為求近似最近鄰查詢(xún)問(wèn)題。

局部敏感哈希算法（LSH，Locality Sensitive Hashing）是一種流行的近似最近鄰查詢(xún)算法。它在高維空間中有優(yōu)異的表現(xiàn)，能夠克服維災(zāi)，且算法的精度和效率能夠滿足應(yīng)用需求。因而在許多應(yīng)用中都有使用，其中有圖像、視頻、音頻和DNA序列等相似性查詢(xún)。

關(guān)于它的研究已有很多年的歷史，除了LSH的應(yīng)用，很多研究者也對(duì)LSH算法進(jìn)行了改進(jìn)，本文將主要介紹集中式下的LSH算法及其改進(jìn)。

2 研究現(xiàn)狀

與基于空間劃分的算法相比，LSH克服了維度災(zāi)難，能夠應(yīng)用在高維數(shù)據(jù)集中，性能也有所提高，因此應(yīng)用的比較廣泛。下面介紹集中式環(huán)境下它的發(fā)展歷程。

2.1 最原始的LSH

LSH是一種概率方法，它的核心是距離近的點(diǎn)哈希到同一桶中的概率會(huì)比距離遠(yuǎn)的點(diǎn)的概率大。通過(guò)這樣的處理方式，可以過(guò)濾掉很多不相似的對(duì)象。

（1）如果D(p,q)≤ r1，則PrH(h(q)=h(p))≥p1；

（2）如果D(p,q)＞r2，則PrH(h(q)=h(p))≤p2。

LSH的處理過(guò)程是將高維空間中的對(duì)象看作點(diǎn)，d是它的維度。從H哈希函 數(shù)族中隨機(jī)獨(dú)立均勻地選擇k個(gè)hi(·)組成函數(shù)g(·)=(h1(·),h2(·),...,hk(·))。通過(guò)哈希函數(shù)g(·)將空間所有 點(diǎn)映射到一個(gè)哈希表T(·)中，哈希表里有多個(gè)桶。選出L個(gè)這樣的函數(shù)g1(·)、g2(·)、…、 gL(·)，每一次把所有的點(diǎn)都哈希到哈希表中，共有L個(gè)哈希表。對(duì)于給定的查詢(xún)q，分別計(jì)算g1(q)、g2(q)、…、gL(q)。以所有落入哈希表Ti(·)中的桶gi(q)中的點(diǎn)作為查詢(xún)候選集，最后比較它們與q之間的距離，距離最近的K個(gè)點(diǎn)即為它的KNN。

最原始的LSH有一些缺點(diǎn)，即 只在海明空間有效、對(duì)參數(shù)k和L敏感、I/O開(kāi)銷(xiāo)大等。

2.2 基于p-穩(wěn)定分布的LSH

在原始LSH方法中，需要將原始空間嵌入到海明空間，而p-穩(wěn)定LSH算法可以直接在歐式空間下進(jìn)行局部敏感哈希運(yùn)算。在p-穩(wěn)定LSH中，利用p-穩(wěn)定分布的特性，使得生成的哈希函數(shù)族可以保持局部敏感性。

哈希函數(shù)族的形式為：

其中向量a的每一維是來(lái)自標(biāo)準(zhǔn)正態(tài)分布N(0,1)， b是[0,w]里的隨機(jī)數(shù)，w為桶寬。根據(jù)不同的a和b，哈希函數(shù)族建立不同的索引。

它把LSH從海明空間擴(kuò)展到歐氏空間，增加了LSH的實(shí)用性。

2.3 多探測(cè)LSH

基于p-穩(wěn)定的LSH能很好地處理歐氏空間的KNN查詢(xún)，但是它需要大量的哈希表以達(dá)到良好的查詢(xún)質(zhì)量。Multi-Probe LSH可以減少算法所需空間。

由局部敏感哈希的性質(zhì)知道，如果一個(gè)對(duì)象靠近查詢(xún)對(duì)象q但沒(méi)有散列到同一個(gè)桶中，則很可能是在與那個(gè)桶“接近”的桶中。因此找到這些“鄰近”桶，就會(huì)增加找到與q近鄰對(duì)象的機(jī)會(huì)。在基本p-穩(wěn)定LSH基礎(chǔ)上，用一個(gè)衍生探測(cè)序列查找有高概率的包含查詢(xún)對(duì)象最近鄰的多個(gè)桶。通過(guò)探測(cè)哈希表中的多個(gè)桶，所需哈希表數(shù)量會(huì)比以前的LSH方法更少，減少了算法的空間消耗。

在有相同查詢(xún)質(zhì)量時(shí)，Multi-probe LSH算法的時(shí)間效率和空間效率都有所減少，這是一種以時(shí)間換空間的方法。

后驗(yàn)多探測(cè)LSH改進(jìn)了多探測(cè)LS H。通過(guò)構(gòu)建一個(gè)包括查詢(xún)對(duì)象以及數(shù)據(jù)集的一些先驗(yàn)知識(shí)的后驗(yàn)概率模型，使得算法能夠更精確地選擇候選桶，減少查找時(shí)間，提高精度和查詢(xún)效率。后驗(yàn)多探測(cè)LSH減少了需要的哈希表數(shù)量和查詢(xún)的時(shí)間。

2.4 基于投影的LSH

計(jì)算向量之間的余弦相似性經(jīng)常采用隨機(jī)投影的方式。首先隨機(jī)選擇1個(gè)每一維都服從高斯分布N(0,1)的超平面r，然后用它與向量v進(jìn)行內(nèi)積運(yùn)算，根據(jù)所得結(jié)果的符號(hào)進(jìn)行取值，即哈希函數(shù)族為h(v)=sgn(v· r)。均勻隨機(jī)地選擇k個(gè)超平面，分別用 上述哈希函數(shù)對(duì)向量進(jìn)行計(jì)算，用這k個(gè)值組成一個(gè)k維的0、1向量，從而達(dá)到降維的效果。

現(xiàn)有的方法大都假設(shè)要哈希的數(shù)據(jù)底層嵌入是明確已知、可計(jì)算的。但是有些數(shù)據(jù)的底層嵌入是隱式知道的。因此沒(méi)法運(yùn)用LSH來(lái)搜索包含核的數(shù)據(jù)。

KLSH為任意核函數(shù)提出了一種基于LSH的技術(shù)，來(lái)執(zhí)行快速相似性檢索。

它的主要思想是構(gòu)造1個(gè)隨機(jī)超平面哈希函數(shù)，在核空間來(lái)進(jìn)行計(jì)算。構(gòu)造是基于中心極限定理的，它用數(shù)據(jù)庫(kù)中的對(duì)象來(lái)計(jì)算近似隨機(jī)向量。由于LSH需要1個(gè)服從特殊高斯分布的隨機(jī)向量，可以用中心極限定理和合適的均值轉(zhuǎn)換和白化轉(zhuǎn)換操作，形成1個(gè)近似隨機(jī)向量。通過(guò)這樣的構(gòu)造，算法能夠用到核空間，也能有效運(yùn)用于大數(shù)據(jù)集中。

但是由KLSH常規(guī)構(gòu)造的隨機(jī)向量只是近似隨機(jī)，且該方法與選擇用于構(gòu)造隨機(jī)向量結(jié)構(gòu)的數(shù)據(jù)庫(kù)對(duì)象數(shù)目有關(guān)。

KLSH只用了1個(gè)核，在現(xiàn)實(shí)多媒體運(yùn)用中會(huì)受到限制。例如，在基于內(nèi)容的多媒體查詢(xún)中，可以從1個(gè)圖像中抽取許多特征。為克服這個(gè)問(wèn)題，BMKLSH采樣多個(gè)核，顯著提高了KLSH的性能。

2.5 基于最小獨(dú)立置換的LSH

最小獨(dú)立置換最早由A Broder提出，它可快速估算2個(gè)集合的相似性。

S為一集合，π為S中元素下標(biāo)的一個(gè)置換，對(duì)于一個(gè)集合A?S，定義哈希函數(shù)為：若給定2個(gè)集合A、B?S，那么Pr[h(A)=h(B)]=J(A,B)（其 中J(A,B)是集合A和B的Jaccard相似性系數(shù)）。

一種最小獨(dú)立置換是Min-Hash。要計(jì)算集合S的最小哈希值，首先用集合的特征矩陣列向量來(lái)表示集合，然后再隨機(jī)置換矩陣的行，把置換順序后第1列為1的索引值作為矩陣的最小哈希值。

2.6 基于哈希函數(shù)改進(jìn)的LSH

由于之前算法的時(shí)間效率不高，F(xiàn)ast LSH旨在提高算法的運(yùn)行時(shí)間。提出了2個(gè)新算法，即ACHash算法和DHHash算法，它們都是基于p-穩(wěn)定LSH改進(jìn)的。應(yīng)用隨機(jī)阿達(dá)馬變換來(lái)加速哈希值的計(jì)算，能在O(dlogd)時(shí)間內(nèi)完成矩陣乘法計(jì)算。

ACHash算法首先用隨機(jī)對(duì)角矩陣和阿達(dá)馬矩陣預(yù)處理輸入向量x，使得處理后的向量變得更密集。然后把所得的向量乘以一個(gè)稀疏高斯矩陣，通過(guò)這樣可以一次得到向量x的k個(gè)哈希值。這k個(gè)哈希值作為g(x)=(h1(x), h2(x),…,hk(x))，得到在相應(yīng)哈希表中的桶號(hào)，加快了計(jì)算時(shí)間。

DHHash算法把查詢(xún)時(shí)間從O(dkL)降到O(dlogd+kL)。與ACHash一樣，用隨機(jī)對(duì)角矩陣D和阿達(dá)瑪變換H來(lái)處理輸入向量。然后乘以隨機(jī)對(duì)角矩陣M和另一個(gè)獨(dú)立的單位高斯矩陣G，最后應(yīng)用另一個(gè)阿達(dá)瑪變換H。最后的哈希函數(shù)為在ACHash的基礎(chǔ)上加快了計(jì)算時(shí)間。

F ast LSH改進(jìn)了LSH算法的計(jì)算時(shí)間，但空間消耗較大，是典型的以空間換時(shí)間。且維度d必須是偶數(shù)，它沒(méi)有考慮參數(shù)的影響。

C2LSH通過(guò)擴(kuò)展Tao Yufei等人之“虛擬哈?！钡木植棵舾泄：瘮?shù)，創(chuàng)造性地將“虛擬哈?！迸c動(dòng)態(tài)碰撞計(jì)數(shù)想法結(jié)合起來(lái)，得到了一個(gè)新的哈希函數(shù)，基于這個(gè)新的哈希函數(shù)來(lái)進(jìn)行近似查詢(xún)。

2.7 基于構(gòu)造新索引結(jié)構(gòu)的LSH

（1）LSB-forest

現(xiàn)有的LSH沒(méi)能同時(shí)保證查詢(xún)質(zhì)量和查詢(xún)效率。LSB-forest卻能夠做到。它的基本思想是相近的對(duì)象有相近的Z-order值。2個(gè)Z-order值間的相近是通過(guò)最長(zhǎng)公共前綴長(zhǎng)度（LLCP）獲得的。

首先，像標(biāo)準(zhǔn)LSH一樣，把d維對(duì)象o用局部敏感哈希函數(shù)G(h1,…,hk)轉(zhuǎn)換成一個(gè)k維的對(duì)象G(o)；然后把每個(gè)G(o)再轉(zhuǎn)換成Z-order值z(mì)(o)，再根據(jù)z(o)建立B-樹(shù)，形成LSB樹(shù)。為達(dá)到查詢(xún)精度，再用L個(gè)LSB-tree構(gòu)造LSB-Forest。

給定查詢(xún)對(duì)象q，LSB-forest算法首先把 它轉(zhuǎn)換成Z-or der值z(mì)(q)，然后用它來(lái)遍歷LSB-forest。由于數(shù)據(jù)庫(kù)中對(duì)象的Z-order存儲(chǔ)在所有L個(gè)LSB樹(shù)中的葉子節(jié)點(diǎn)中，按照與z(q)之間的LLCP遞減的順序訪問(wèn)這些Z-order值。

（2）HashFile

LSB-forest索 引采用隨機(jī)I/O訪問(wèn)。當(dāng)多媒體數(shù)據(jù)庫(kù)很大時(shí)，它需要相當(dāng)大的磁盤(pán)I/O成本以獲得好的結(jié)果。D Zhang等人為多媒體對(duì)象有效檢索，提出了一種新的索引結(jié)構(gòu)——HashFile。它結(jié)合隨機(jī)投影和線性掃描的優(yōu)點(diǎn)，不像LSH家族那樣每個(gè)桶串聯(lián)k個(gè)Hash值，它只遞歸分割密集的桶，并把它們組織為一個(gè)樹(shù)形結(jié)構(gòu)。給定查詢(xún)點(diǎn)q，查詢(xún)算法以自頂向下的方式查詢(xún)與查詢(xún)對(duì)象鄰近的桶。每個(gè)節(jié)點(diǎn)的候選桶以哈希值遞增的順序存儲(chǔ)，可以有效地加載到內(nèi)存中做線性掃描。HashFile可以支持精確的和近似的NN查詢(xún)。

（3）SK-LSH

SK-LSH針對(duì)訪問(wèn)候選對(duì)象需要很大的I/O開(kāi)銷(xiāo)問(wèn)題，提出一種基于局部敏感哈希的外存索引方法。通過(guò)給哈希鍵值g(·)設(shè)計(jì)一種新的度量方法，使得起哈希鍵值像自然數(shù)那樣有序，通過(guò)把與g(·)距離相近的對(duì)象存儲(chǔ)在一個(gè)索引文件中，能夠在一個(gè)哈希表中找出更多候選對(duì)象，大幅度降低了存儲(chǔ)和I/O開(kāi)銷(xiāo)。

（4）Bi-level LSH

Bi-level是基于兩級(jí)哈希的。第一級(jí)，使用RP-樹(shù)將數(shù)據(jù)集劃分成具有有界縱橫比的小組，并用于計(jì)算良好分隔的簇，讓那些相似元素聚在一起。第二級(jí)，用基于空間填充曲線的層次結(jié)構(gòu)計(jì)算每個(gè)小組的單個(gè)LSH哈希表。給定一個(gè)查詢(xún)時(shí)，首先要確定相應(yīng)的小組，在相應(yīng)小組合適的LSH哈希表桶內(nèi)執(zhí)行K近鄰搜索。算法能很好地映射到目前的GPU架構(gòu)中，并能提高近似KNN查詢(xún)質(zhì)量。

2.8 基于改進(jìn)參數(shù)的LSH

LSH算法中的參數(shù)包括哈希函數(shù)個(gè)數(shù)k、桶寬w以及哈希表的數(shù)量L。它們會(huì)影響查詢(xún)的精度和效率，許多研究者對(duì)如何選擇合適的參數(shù)做了相應(yīng)的研究。

LSH Forest避免調(diào)整參數(shù)k，通過(guò)用前綴樹(shù)表示哈希表，參數(shù)k是通過(guò)計(jì)算相應(yīng)前綴樹(shù)的葉節(jié)點(diǎn)的深度來(lái)獲得的。Modeling LSH對(duì)多探測(cè)LSH進(jìn)行建模，根據(jù)數(shù)據(jù)集的分布來(lái)選擇合適的參數(shù)，實(shí)現(xiàn)參數(shù)的自動(dòng)調(diào)整。M Slaney從2個(gè)直方圖開(kāi)始分析，用一個(gè)簡(jiǎn)單的計(jì)算成本模型，返回LSH參數(shù)，使得LSH索引滿足性能要求。BayesLSH通過(guò)把相似性s看成是一個(gè)待估計(jì)的參數(shù)，根據(jù)先驗(yàn)知識(shí)s會(huì)有一個(gè)先驗(yàn)分布p(s)。后通過(guò)多次實(shí)驗(yàn)，利用Bayes公式對(duì)先驗(yàn)分布進(jìn)行調(diào)整，得到s的后驗(yàn)分布。它能夠在比較前幾個(gè)哈希值之后，剪枝掉多數(shù)假陽(yáng)性節(jié)點(diǎn)，并自動(dòng)調(diào)整需要比較的哈希函數(shù)個(gè)數(shù)。

3 局部敏感哈希的應(yīng)用

由于LSH在高維空間中有優(yōu)異的表現(xiàn)，能夠克服維災(zāi)，且算法的精度和效率能夠滿足應(yīng)用需求。因而在許多應(yīng)用中都有使用，其中有圖像、視頻、音頻和DNA序列等相似性查詢(xún)。

LSH在信息檢索領(lǐng)域中有非常廣泛的應(yīng)用。Y Yu使用兩級(jí)LSH索引對(duì)音軌進(jìn)行處理。W Jeon使用它對(duì)音頻進(jìn)行近似查詢(xún)，利用LSH對(duì)語(yǔ)音文檔主題進(jìn)行分類(lèi)。一些視頻重復(fù)檢測(cè)系統(tǒng)中同樣采用LSH。在衛(wèi)星圖像檢索中，R Buaba也使用了LSH。Y Lin利用LSH對(duì)漢字書(shū)法圖片進(jìn)行處理。

G S Manku使用LSH對(duì)網(wǎng)頁(yè)數(shù)據(jù)進(jìn)行重復(fù)檢測(cè)。N Sundaram使用LSH對(duì)數(shù)據(jù)流的相似性進(jìn)行處理。谷歌新聞使用最小哈希對(duì)新聞進(jìn)行協(xié)同過(guò)濾處理。在生物研究中，DNA序列的相似性匹配同樣采用LSH。Rasheed使用LSH對(duì)物種多樣性進(jìn)行相似性估計(jì)。

LSH還被用于對(duì)大規(guī)模、高維數(shù)據(jù)集進(jìn)行離群點(diǎn)檢測(cè)。湯春蕾使用LSH進(jìn)行時(shí)間序列的相似性搜索。

4 結(jié)束語(yǔ)

本文介紹了LSH算法和它的改進(jìn)算法。LSH在高維空間中有優(yōu)異的表現(xiàn)，并且能夠克服維災(zāi)，且算法的精度和效率能夠滿足應(yīng)用需求，具有很高的實(shí)用價(jià)值。

LSH的改進(jìn)算法有用時(shí)間換取空間的，有用空間換取時(shí)間的，有在兩個(gè)方面都進(jìn)行了優(yōu)化的。雖然這些算法都對(duì)LSH做了改進(jìn)，但仍然缺乏完善的理論以明確地保證搜索質(zhì)量。一些算法只對(duì)某些特殊數(shù)據(jù)有效，所以在使用時(shí)選擇合適的參數(shù)很困難。如何選擇合適的參數(shù)將會(huì)是一個(gè)很好的研究方向。

原有LSH方法的隨機(jī)I/O開(kāi)銷(xiāo)很大，如何設(shè)計(jì)有效的外存索引結(jié)構(gòu)也是個(gè)很好的問(wèn)題。隨著大數(shù)據(jù)的發(fā)展，把LSH應(yīng)用到分布式環(huán)境中也會(huì)是個(gè)很好的研究課題。

[1] P Indyk, R Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality[C]. Proceedings of the thirtieth annual ACM symposium on theory of computing. ACM, 1998: 604-613.

[2] A Gionis, P Indyk, R Motwani. Similarity search in high dimensions via hashing[J]. VLDB, 1999: 518-529.

[3] M Datar, N Immorlica, P Indyk, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]. Proceedings of the twentieth annual symposium on computational geometry. ACM, 2004: 253-262.

[4] Q Lv, W Josephson, Z Wang, et al. Multi-probe LSH: efficient indexing for high-dimensional similarity search[C]. Proceedings of the 33rd international conference on very large data bases. VLDB Endowment, 2007: 950-961.

[5] A Joly and O Buisson. A posteriori multi-probe locality sensitive hashing[C]. Proceedings of the 16th ACM international conference on multimedia. ACM, 2008: 209-218.

[6] M S Charikar. Similarity estimation techniques from rounding algorithms[C]. in Proceedings of the thirtyfourth annual ACM symposium on theory of computing. ACM, 2002: 380-388.

[7] B Kulis, K Grauman. Kernelized locality-sensitive hashing for scalable image search[C]. Computer Vision, 2009 IEEE 12th International Conference on. IEEE, 2009: 2130-2137.

[8] H Xia, P Wu, S C Hoi, et al. Boosting multi-kernel locality-sensitive hashing for scalable image retrieval[C]. Proceedings of the 35th international ACM SIGIR conference on research and development in information retrieval. ACM, 2012: 55-64.

[9] A Z Broder, M Charikar, A M Frieze, et al. Min-wise independent permutations[C]. Proceedings of the thirtieth annual ACM symposium on theory of computing. ACM, 1998: 327-336.

[10] A Dasgupta, R Kumar, T Sarlós. Fast locality-sensitive hashing[C]. Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, 2011: 1073-1081.

[11] J Gan, J Feng, Q Fang, et al. Locality-sensitive hashing scheme based on dynamic collision counting[C]. Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM, 2012: 541-552.

[12] Y Tao, K Yi, C Sheng, et al. Quality and efficiency in high dimensional nearest neighbor search[C]. Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. ACM, 2009: 563-576.

[13] D Zhang, D Agrawal, G Chen, et al. Hashfile: An efficient index structure for multimedia data[C]. Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011: 1103-1114.

[14] Y Liu, J Cui, Z Huang, et al. Sk-lsh: An effi cient index structure for approximate nearest neighbor search[J]. Proceedings of the VLDB Endowment, 2014,7(9): 745-756.

[15] J Pan, D Manocha. Fast GPU-based locality sensitive hashing for k-nearest neighbor computation[C]. Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2011: 211-220.

[16] J Pan, D Manocha. Bi-level locality sensitive hashing for k-nearest neighbor computation[C]. Data Engineering(ICDE), 2012 IEEE 28th International Conference on, 2012: 378-389.

[17] M Bawa, T Condie, P Ganesan. LSH forest: self-tuning indexes for similarity search[C]. Proceedings of the 14th international conference on World Wide Web. ACM, 2005: 651-660.

[18] W Dong, Z Wang, W Josephson, et al. Modeling LSH for performance tuning[C]. Proceedings of the 17th ACM conference on information and knowledge management. ACM, 2008: 669-678.

[19] M Slaney, Y Lifshits, J He. Optimal Parameters for Locality-Sensitive Hashing[J]. Proceedings of the IEEE, 2012,100(9): 2604-2623.

[20] V Satuluri, S Parthasarathy. Bayesian locality sensitive hashing for fast similarity search[J]. Proceedings of theVLDB Endowment, 2012,5(5): 430-441.

[21] Y Yu, M Crucianu, V Oria, et al. Local summarization and multi-level LSH for retrieving multi-variant audio tracks[C]. Proceedings of the 17th ACM international conference on Multimedia. ACM, 2009: 341-350.

[22] W Jeon, Y M Cheng. Efficient speaker search over large populations using kernelized locality-sensitive hashing[C]. Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on. IEEE, 2012: 4261-4264.

[23] 何學(xué)文. 基于LSH的語(yǔ)音文檔主題分類(lèi)研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2012.

[24] Z Liu, T Liu, D C Gibbon, et al. Effective and scalable video copy detection[C]. Proceedings of the international conference on multimedia information retrieval. ACM, 2010: 119-128.

[25] S Paisitkriangkrai, T Mei, J Zhang, et al. Scalable clipbased near-duplicate video detection with ordinal measure[C]. Proceedings of the ACM International Conference on Image and Video Retrieval. ACM, 2010: 121-128.

[26] R Buaba, M Gebril, A Homaifar, et al. Locality sensitive hashing for satellite images using texture feature vectors[C]. Aerospace Conference, IEEE, 2010: 1-10.

[27] R Buaba, A Homaifar, M Gebril, et al. Satellite image retrieval using low memory locality sensitive hashing in Euclidean space[J]. Earth Science Informatics, 2011,4(1): 17-28.

[28] Lin Y, Wu J, Gao P, et al. LSH-based large scale chinese calligraphic character recognition[C]. Proceedings of the 13th ACM/IEEE-CS joint conference on Digital libraries. ACM, 2013: 323-330.

[29] G S Manku, A Jain, A Das Sarma. Detecting nearduplicates for web crawling[C]. Proceedings of the 16th international conference on World Wide Web. ACM, 2007: 141-150.

[30] Sundaram N, Turmukhametova A, Satish N, et al. Streaming similarity search over one billion tweets using parallel locality-sensitive hashing[J]. Proceedings of the VLDB Endowment, 2013,6(14): 1930-1941.

[31] A S Das, M Datar, A Garg, et al. Google news personalization: scalable online collaborative filtering[C]. Proceedings of the 16th international conference on World Wide Web. ACM, 2007: 271-280.

[32] J Buhler. Effi cient large-scale sequence comparison by locality-sensitive hashing[J]. Bioinformatics, 2001,17(5): 419-428.

[33] J Buhler. Provably sensitive indexing strategies for biosequence similarity search[J]. Journal of Computational Biology, 2003,10(3-4): 399-417.

[34] Z Rasheed, H Rangwala, D Barbara. LSH-Div: species diversity estimation using locality sensitive hashing[C]. Bioinformatics and Biomedicine(BIBM), 2012 IEEE International Conference on, 2012: 1-6.

[35] Z Rasheed, H Rangwala, D Barbara. Effi cient Clustering of Metagenomic Sequences using Locality Sensitive Hashing[C]. SDM, 2012: 1023-1034.

[36] Y Wang, S Parthasarathy, S Tatikonda. Locality Sensitive Outlier Detection: A ranking driven approach[C]. Data Engineering (ICDE), 2011 IEEE 27th International Conference on, 2011: 410-421.

[37] 湯春蕾,董家麒. 基于LSH的時(shí)間子序列查詢(xún)算法[J].計(jì)算機(jī)學(xué)報(bào), 2012,35(11): 2228-2236. ★

Review on Locality Sensitive Hashing in Centralized Environment

LIU Gen-ping
(Ningbo University, Ningbo 315211, China)

Locality sensitive hashing is a very popular high dimensional similarity search algorithm. LSH algorithm and its implementation in centralized environment were introduced. Features, advantages and disadvantages of LSH algorithm were analyzed by summarizing several published papers. LSH algorithm was proved to be effective in widespread applications of approximate nearest neighbor query.

high dimensional data similarity search KNN query locality sensitive hashing

10.3969/j.issn.1006-1010.2015.10.009

TP391

A

1006-1010(2015)10-0046-06

劉根平. 集中式環(huán)境下的局部敏感哈希算法綜述[J]. 移動(dòng)通信, 2015,39(10): 46-51.

寧波市自然科學(xué)基金（2014A610023）

2015-03-20

責(zé)任編輯：劉妙 liumiao@mbcom.cn

劉根平：碩士研究生就讀于寧波大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專(zhuān)業(yè)，研究方向?yàn)閿?shù)據(jù)挖掘。