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

劉根平

（寧波大學，浙江 寧波 315211）

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

劉根平

（寧波大學，浙江 寧波 315211）

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

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

1 引言

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

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

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

關于它的研究已有很多年的歷史，除了LSH的應用，很多研究者也對LSH算法進行了改進，本文將主要介紹集中式下的LSH算法及其改進。

2 研究現(xiàn)狀

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

2.1 最原始的LSH

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

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

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

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

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

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

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

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

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

它把LSH從海明空間擴展到歐氏空間，增加了LSH的實用性。

2.3 多探測LSH

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

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

在有相同查詢質量時，Multi-probe LSH算法的時間效率和空間效率都有所減少，這是一種以時間換空間的方法。

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

2.4 基于投影的LSH

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

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

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

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

但是由KLSH常規(guī)構造的隨機向量只是近似隨機，且該方法與選擇用于構造隨機向量結構的數(shù)據庫對象數(shù)目有關。

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

2.5 基于最小獨立置換的LSH

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

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

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

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

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

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

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

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

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

2.7 基于構造新索引結構的LSH

（1）LSB-forest

現(xiàn)有的LSH沒能同時保證查詢質量和查詢效率。LSB-forest卻能夠做到。它的基本思想是相近的對象有相近的Z-order值。2個Z-order值間的相近是通過最長公共前綴長度（LLCP）獲得的。

首先，像標準LSH一樣，把d維對象o用局部敏感哈希函數(shù)G(h1,…,hk)轉換成一個k維的對象G(o)；然后把每個G(o)再轉換成Z-order值z(o)，再根據z(o)建立B-樹，形成LSB樹。為達到查詢精度，再用L個LSB-tree構造LSB-Forest。

給定查詢對象q，LSB-forest算法首先把 它轉換成Z-or der值z(q)，然后用它來遍歷LSB-forest。由于數(shù)據庫中對象的Z-order存儲在所有L個LSB樹中的葉子節(jié)點中，按照與z(q)之間的LLCP遞減的順序訪問這些Z-order值。

（2）HashFile

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

（3）SK-LSH

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

（4）Bi-level LSH

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

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

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

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

3 局部敏感哈希的應用

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

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

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

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

4 結束語

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

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

原有LSH方法的隨機I/O開銷很大，如何設計有效的外存索引結構也是個很好的問題。隨著大數(shù)據的發(fā)展，把LSH應用到分布式環(huán)境中也會是個很好的研究課題。

[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] 何學文. 基于LSH的語音文檔主題分類研究[D]. 哈爾濱: 哈爾濱工程大學, 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的時間子序列查詢算法[J].計算機學報, 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]. 移動通信, 2015,39(10): 46-51.

寧波市自然科學基金（2014A610023）

2015-03-20

責任編輯：劉妙 liumiao@mbcom.cn

劉根平：碩士研究生就讀于寧波大學計算機應用技術專業(yè)，研究方向為數(shù)據挖掘。