Locality Sensitive Hash

局部敏感哈希——Locality Sensitive Hash是一种常见的用于处理高维向量的索引办法。与其它基于Tree的数据结构，诸如KD-Tree、SR-Tree相比，它较好地克服了Curse of Dimension，能够将KNN的时间复杂度缩减到sub-linear。LSH多被用于文本、多媒体（图像、音频）的相似性判断。请看下图：



参考上图，如果我们要返回距离中心为r的点，LSH会返回给我们范围更远、更多的点，也就是说，LSH返回的结果会带有一定的false positive。我们或许需要使用linear search进行二次筛选，但这毕竟大大减少了计算的时间。

由此可见，LSH与一般的加密型哈希函数有很大的区别，参见下图：



一种实现LSH的最简单的方式是采用random bits sampling的方式，即将待索引的多维整型向量转化为0或1的字符串；再采用随机选取其中的K位拼接成新的字符串；最后再采用常规的哈希函数（例如MD5）等算法获取带索引向量的LSH Code。这样的Hash Code有一个特点，就是Hamming Distance相近的两个向量，其冲突的概率越大，即结果相等的可能性越大。为了减少增强KNN搜索的能力，与Bloom Filter类似，采用多个Hash Table增加冲突的概率，参见下图：



来看一下LSH的复杂度：



可见，与各种其它的数据结构相比，基于lsh的索引结构的query时间复杂度，可以做到与向量维度无关，有效地克服了维度灾难的问题，因此更适合高维向量的索引。

基于LSH实现的图像近似检索，其原理也很类似，如下图所示：






时间关系，下次有空会把LSH的java implementation放上来。

评论

2 楼 cong2008abc 2013-10-30  

请问你的代码上传到哪里了？

1 楼 jiasen_huo 2012-04-27  

您觉得这个算法 实现起来难吗 怎么我看到MIT的实现代码那么长啊