转载

局部敏感哈希之分层法与哈希码法

学到现在越来越感觉计算机网络、操作系统的重要性，组成原理到没感觉出来，求推荐资料，我想要的是描述性解释，教材不是我想要的，谢谢！

感觉自己的知识很老旧，在没有出国也没去高水平大学的条件下，只能通过网络学习了，感谢博客园。

一.检索分类

在检索技术中，索引一直需要研究的核心技术。当下，索引技术主要分为三类：基于树的索引技术（tree-based index）、基于哈希的索引技术（hashing-based index）与基于词的倒排索引（visual words based inverted index）。本文主要对哈希索引技术进行介绍。

二.哈希概述

在检索中，需要解决的问题是给定一个查询样本query，返回与此query相似的样本，线性搜索耗时耗力，不能承担此等重任，要想快速找到结果，必须有一种方法可以将搜索空间控制到一个可以接受的范围，哈希在检索中就是承担这样的任务，因而，这些哈希方法一般都是局部敏感（Locality-sensitive）的，即样本越相似，经过哈希后的值越有可能一样。所以，本文中介绍的技术都是局部敏感哈希（Locality Sensitive Hashing，LSH），与hashmap、hashtable等数据结构中的哈希函数有所不同。

三.哈希分类

对于哈希技术，可以按照不同的维度对齐进行划分。

按照其在检索技术中的应用方法来划分，可以分为分层法和哈希码法：

3.1分层法

分层法即为在数据查询过程中使用哈希技术在中间添加一层，将数据划分到桶中；在查询时，先对query计算桶标号，找到与query处于同一个桶的所有样本，然后按照样本之间的相似度计算方法（比如欧氏距离、余弦距离等）使用原始数据计算相似度，按照相似度的顺序返回结果，在该方法中，通常是一组或一个哈希函数形成一个表，表内有若干个桶，可以使用多个表来提高查询的准确率，但通常这是以时间为代价的。分层法的示意图如图1所示。在图1中，H1、H2等代表哈希表，g1、g2等代表哈希映射函数。分层法的代表算法为E2LSH。

3.2 哈希码法

哈希码法则是使用哈希码来代替原始数据进行存储，在分层法中，原始数据仍然需要以在第二层被用来计算相似度，而哈希码法不需要，它使用LSH函数直接将原始数据转换为哈希码，在计算相似度的时候使用hamming距离来衡量。转换为哈希码之后的相似度计算非常之快，比如，可以使用64bit整数来存储哈希码，计算相似度只要使用同或操作就可以得到，唰唰唰，非常之快，忍不住用拟声词来表达我对这种速度的难言之喜，还望各位读者海涵。

哈希码法的代表算法有很多，比如KLSH、Semantic Hashing、KSH等。

3.3 区别

1.在对哈希函数的要求上，哈希码方法对哈希函数的要求更高，因为在分层法中，即便哈希没有计算的精确，后面还有原始数据直接计算相似度来保底，得到的结果总不会太差，而哈希码没有后备保底的，胜则胜败则败。

2.在查询的时间复杂度上，分层法的时间复杂度主要在找到桶后的样本原始数据之间的相似度计算，而哈希码则主要在query的哈希码与所有样本的哈希码之间的hamming距离的相似计算。哈希码法没有太多其他的需要，但分层法中的各个桶之间相对较均衡方能使复杂度降到最低。按照我的经验，在100W的5000维数据中，KSH比E2LSH要快一个数量级。

3.在哈希函数的使用上，两者使用的哈希函数往往可以互通，E2LSH使用的p-stable LSH函数可以用到哈希码方法上，而KSH等哈希方法也可以用到分层法上去。

4.按照哈希函数来划分，可以分为无监督和有监督两种：

无监督，哈希函数是基于某种概率理论的，可以达到局部敏感效果。如E2LSH等。

有监督，哈希函数是从数据中学习出来的，如KSH、Semantic Hashing等。

一般来说，有监督算法比无监督算法更加精确，因而也更常用于哈希码法中。

部分参考文献http://dataunion.org/12912.html

四.遗留问题

把局部敏感哈希用在最近邻查询中。

现在的问题是，1.为什么需要多个表？为何能提高准确率吗？2.p稳定分布的具体例子3.需要多个表，每个表内又是好多桶(除以w分桶)，那么查找最近邻的时候是对每个表分别查一次么，然后去结果并集，貌似不是这样啊？那要多个表干什么？4.文章说多个哈希函数，每个函数残生一个实数，最后要相乘然后连加最后取余，把向量映射为实数放于桶内，既然每个表内的哈希函数不一致，那么最后取余的值也不一样，也就是说每个数据在每个表内的值都不一样，那么问题来了，对于某一个查询点经过一次相同哈希，但是却要在每个表内查询，但是每个表内的哈希都是和查询电使用不一样的啊，这样有意义么？如果不是这样，是下面这样：某个查询电分别使用每个表内的哈希进行查询，这样要多个表还有意义么？

联系方式：791909235@qq.com，13137910179

正文到此结束