集中式环境下的局部敏感哈希算法综述*

2015-12-19刘根平

移动通信 2015年10期

关键词：哈希相似性向量

刘根平

（宁波大学，浙江宁波 315211）

集中式环境下的局部敏感哈希算法综述*

刘根平

（宁波大学，浙江宁波 315211）

局部敏感哈希算法是一种很流行的高维相似性查找算法。通过总结多篇已发表论文，介绍了集中式环境下的局部敏感哈希算法及其实现，分析了各种局部敏感哈希算法的特点和优缺点。在近似最近邻查询中的广泛应用证实了局部敏感哈希算法的有效性。

高维数据相似性搜索 KNN查询局部敏感哈希算法

1 引言

近年来，随着互联网的快速发展，产生的数据数以万计。如何从庞大的数据中挖掘出有用的信息，显得尤为重要，如在图像数据库中寻找内容相似或者语意相关的图像。相似性查询算法的研究成为众多研究者研究的内容，是一个很有意义的研究方向。

在解决最近邻查询问题中，经常用到的方法有传统的基于树（如k-d tree等）的空间划分算法。这些传统的方法在数据维度较低时性能良好，然而在维度超过10以后，算法的性能会迅速下降，有时甚至不如暴力算法。为解决高维数据问题，有人提出可以使用精度来换效率。这样把求最近邻问题转化为求近似最近邻查询问题。

局部敏感哈希算法（LSH，Locality Sensitive Hashing）是一种流行的近似最近邻查询算法。它在高维空间中有优异的表现，能够克服维灾，且算法的精度和效率能够满足应用需求。因而在许多应用中都有使用，其中有图像、视频、音频和DNA序列等相似性查询。

关于它的研究已有很多年的历史，除了LSH的应用，很多研究者也对LSH算法进行了改进，本文将主要介绍集中式下的LSH算法及其改进。

2 研究现状

与基于空间划分的算法相比，LSH克服了维度灾难，能够应用在高维数据集中，性能也有所提高，因此应用的比较广泛。下面介绍集中式环境下它的发展历程。

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哈希函数族中随机独立均匀地选择k个hi(·)组成函数g(·)=(h1(·),h2(·),...,hk(·))。通过哈希函数g(·)将空间所有点映射到一个哈希表T(·)中，哈希表里有多个桶。选出L个这样的函数g1(·)、g2(·)、…、 gL(·)，每一次把所有的点都哈希到哈希表中，共有L个哈希表。对于给定的查询q，分别计算g1(q)、g2(q)、…、gL(q)。以所有落入哈希表Ti(·)中的桶gi(q)中的点作为查询候选集，最后比较它们与q之间的距离，距离最近的K个点即为它的KNN。

最原始的LSH有一些缺点，即只在海明空间有效、对参数k和L敏感、I/O开销大等。

2.2 基于p-稳定分布的LSH

在原始LSH方法中，需要将原始空间嵌入到海明空间，而p-稳定LSH算法可以直接在欧式空间下进行局部敏感哈希运算。在p-稳定LSH中，利用p-稳定分布的特性，使得生成的哈希函数族可以保持局部敏感性。

哈希函数族的形式为：

其中向量a的每一维是来自标准正态分布N(0,1)， b是[0,w]里的随机数，w为桶宽。根据不同的a和b，哈希函数族建立不同的索引。

它把LSH从海明空间扩展到欧氏空间，增加了LSH的实用性。

2.3 多探测LSH

基于p-稳定的LSH能很好地处理欧氏空间的KNN查询，但是它需要大量的哈希表以达到良好的查询质量。Multi-Probe LSH可以减少算法所需空间。

由局部敏感哈希的性质知道，如果一个对象靠近查询对象q但没有散列到同一个桶中，则很可能是在与那个桶“接近”的桶中。因此找到这些“邻近”桶，就会增加找到与q近邻对象的机会。在基本p-稳定LSH基础上，用一个衍生探测序列查找有高概率的包含查询对象最近邻的多个桶。通过探测哈希表中的多个桶，所需哈希表数量会比以前的LSH方法更少，减少了算法的空间消耗。

在有相同查询质量时，Multi-probe LSH算法的时间效率和空间效率都有所减少，这是一种以时间换空间的方法。

后验多探测LSH改进了多探测LS H。通过构建一个包括查询对象以及数据集的一些先验知识的后验概率模型，使得算法能够更精确地选择候选桶，减少查找时间，提高精度和查询效率。后验多探测LSH减少了需要的哈希表数量和查询的时间。

2.4 基于投影的LSH

计算向量之间的余弦相似性经常采用随机投影的方式。首先随机选择1个每一维都服从高斯分布N(0,1)的超平面r，然后用它与向量v进行内积运算，根据所得结果的符号进行取值，即哈希函数族为h(v)=sgn(v· r)。均匀随机地选择k个超平面，分别用上述哈希函数对向量进行计算，用这k个值组成一个k维的0、1向量，从而达到降维的效果。

现有的方法大都假设要哈希的数据底层嵌入是明确已知、可计算的。但是有些数据的底层嵌入是隐式知道的。因此没法运用LSH来搜索包含核的数据。

KLSH为任意核函数提出了一种基于LSH的技术，来执行快速相似性检索。

它的主要思想是构造1个随机超平面哈希函数，在核空间来进行计算。构造是基于中心极限定理的，它用数据库中的对象来计算近似随机向量。由于LSH需要1个服从特殊高斯分布的随机向量，可以用中心极限定理和合适的均值转换和白化转换操作，形成1个近似随机向量。通过这样的构造，算法能够用到核空间，也能有效运用于大数据集中。

但是由KLSH常规构造的随机向量只是近似随机，且该方法与选择用于构造随机向量结构的数据库对象数目有关。

KLSH只用了1个核，在现实多媒体运用中会受到限制。例如，在基于内容的多媒体查询中，可以从1个图像中抽取许多特征。为克服这个问题，BMKLSH采样多个核，显著提高了KLSH的性能。

2.5 基于最小独立置换的LSH

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

S为一集合，π为S中元素下标的一个置换，对于一个集合A⊆S，定义哈希函数为：若给定2个集合A、B⊆S，那么Pr[h(A)=h(B)]=J(A,B)（其中J(A,B)是集合A和B的Jaccard相似性系数）。

一种最小独立置换是Min-Hash。要计算集合S的最小哈希值，首先用集合的特征矩阵列向量来表示集合，然后再随机置换矩阵的行，把置换顺序后第1列为1的索引值作为矩阵的最小哈希值。

2.6 基于哈希函数改进的LSH

由于之前算法的时间效率不高，Fast LSH旨在提高算法的运行时间。提出了2个新算法，即ACHash算法和DHHash算法，它们都是基于p-稳定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。最后的哈希函数为在ACHash的基础上加快了计算时间。

F ast LSH改进了LSH算法的计算时间，但空间消耗较大，是典型的以空间换时间。且维度d必须是偶数，它没有考虑参数的影响。

C2LSH通过扩展Tao Yufei等人之“虚拟哈希”的局部敏感哈希函数，创造性地将“虚拟哈希”与动态碰撞计数想法结合起来，得到了一个新的哈希函数，基于这个新的哈希函数来进行近似查询。

2.7 基于构造新索引结构的LSH

（1）LSB-forest

现有的LSH没能同时保证查询质量和查询效率。LSB-forest却能够做到。它的基本思想是相近的对象有相近的Z-order值。2个Z-order值间的相近是通过最长公共前缀长度（LLCP）获得的。

首先，像标准LSH一样，把d维对象o用局部敏感哈希函数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。由于数据库中对象的Z-order存储在所有L个LSB树中的叶子节点中，按照与z(q)之间的LLCP递减的顺序访问这些Z-order值。

（2）HashFile

LSB-forest索引采用随机I/O访问。当多媒体数据库很大时，它需要相当大的磁盘I/O成本以获得好的结果。D Zhang等人为多媒体对象有效检索，提出了一种新的索引结构——HashFile。它结合随机投影和线性扫描的优点，不像LSH家族那样每个桶串联k个Hash值，它只递归分割密集的桶，并把它们组织为一个树形结构。给定查询点q，查询算法以自顶向下的方式查询与查询对象邻近的桶。每个节点的候选桶以哈希值递增的顺序存储，可以有效地加载到内存中做线性扫描。HashFile可以支持精确的和近似的NN查询。

（3）SK-LSH

SK-LSH针对访问候选对象需要很大的I/O开销问题，提出一种基于局部敏感哈希的外存索引方法。通过给哈希键值g(·)设计一种新的度量方法，使得起哈希键值像自然数那样有序，通过把与g(·)距离相近的对象存储在一个索引文件中，能够在一个哈希表中找出更多候选对象，大幅度降低了存储和I/O开销。

（4）Bi-level LSH

Bi-level是基于两级哈希的。第一级，使用RP-树将数据集划分成具有有界纵横比的小组，并用于计算良好分隔的簇，让那些相似元素聚在一起。第二级，用基于空间填充曲线的层次结构计算每个小组的单个LSH哈希表。给定一个查询时，首先要确定相应的小组，在相应小组合适的LSH哈希表桶内执行K近邻搜索。算法能很好地映射到目前的GPU架构中，并能提高近似KNN查询质量。

2.8 基于改进参数的LSH

LSH算法中的参数包括哈希函数个数k、桶宽w以及哈希表的数量L。它们会影响查询的精度和效率，许多研究者对如何选择合适的参数做了相应的研究。

LSH Forest避免调整参数k，通过用前缀树表示哈希表，参数k是通过计算相应前缀树的叶节点的深度来获得的。Modeling LSH对多探测LSH进行建模，根据数据集的分布来选择合适的参数，实现参数的自动调整。M Slaney从2个直方图开始分析，用一个简单的计算成本模型，返回LSH参数，使得LSH索引满足性能要求。BayesLSH通过把相似性s看成是一个待估计的参数，根据先验知识s会有一个先验分布p(s)。后通过多次实验，利用Bayes公式对先验分布进行调整，得到s的后验分布。它能够在比较前几个哈希值之后，剪枝掉多数假阳性节点，并自动调整需要比较的哈希函数个数。

3 局部敏感哈希的应用

由于LSH在高维空间中有优异的表现，能够克服维灾，且算法的精度和效率能够满足应用需求。因而在许多应用中都有使用，其中有图像、视频、音频和DNA序列等相似性查询。

LSH在信息检索领域中有非常广泛的应用。Y Yu使用两级LSH索引对音轨进行处理。W Jeon使用它对音频进行近似查询，利用LSH对语音文档主题进行分类。一些视频重复检测系统中同样采用LSH。在卫星图像检索中，R Buaba也使用了LSH。Y Lin利用LSH对汉字书法图片进行处理。

G S Manku使用LSH对网页数据进行重复检测。N Sundaram使用LSH对数据流的相似性进行处理。谷歌新闻使用最小哈希对新闻进行协同过滤处理。在生物研究中，DNA序列的相似性匹配同样采用LSH。Rasheed使用LSH对物种多样性进行相似性估计。

LSH还被用于对大规模、高维数据集进行离群点检测。汤春蕾使用LSH进行时间序列的相似性搜索。

4 结束语

本文介绍了LSH算法和它的改进算法。LSH在高维空间中有优异的表现，并且能够克服维灾，且算法的精度和效率能够满足应用需求，具有很高的实用价值。

LSH的改进算法有用时间换取空间的，有用空间换取时间的，有在两个方面都进行了优化的。虽然这些算法都对LSH做了改进，但仍然缺乏完善的理论以明确地保证搜索质量。一些算法只对某些特殊数据有效，所以在使用时选择合适的参数很困难。如何选择合适的参数将会是一个很好的研究方向。

原有LSH方法的随机I/O开销很大，如何设计有效的外存索引结构也是个很好的问题。随着大数据的发展，把LSH应用到分布式环境中也会是个很好的研究课题。

[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