哈希检索
一.哈希检索概述
LSH是Locality Sensitive Hashing这一术语的常见缩写形式；也可译作局部敏感哈希；基于具备特定局部敏感特性的哈希函数设计；以提高相似性搜索效率；尽管自首次提出至今不足二十余年；但由于其独特的局部敏感特性；特别是在处理高维数据时展现出与k-d树等方法类似的高效性能；因此已被广泛应用于多种检索场景（涵盖文本、音频、图片、视频以及基因研究等多种领域）。
1.1 检索分类
在信息检索系统中，索引始终是研究的核心内容。当前阶段下，在信息检索领域内主要存在以下三种类型的索引体系：第一种是基于树状结构的信息组织方式；第二种是采用哈希表结构实现的数据映射方法；第三种则是通过视觉单词构建反向指数的技术模式。
在检索领域中存在一个关键问题：当给定一个查询样本query时，请返回与之相似的样本集合。由于线性搜索的方式不仅费时费力而且难以应对大量数据查询的需求，在提高检索效率方面存在明显局限性。因此需要一种能够有效控制搜索空间的方法来实现这一目标。在检索算法中哈希技术发挥着关键作用：它通过将数据映射至特定的空间从而实现对相似数据的高效识别与聚类工作。这种方法的核心特征在于其局部敏感性即只有当输入数据具有较高的相似度时其对应的哈希值才会高度重叠从而保证了检索结果的质量同时显著提升了匹配效率
1.2 分层法与哈希码法
对于哈希技术的主要依据是根据不同的维度进行分类或归类。在信息处理领域中, 依据其在检索技术中的应用方式来进行分类或归类, 可以将信息存储机制划分为两大类:一种是基于分层结构的设计方案, 另一种则是基于哈希码的实现方案.
分层法即是通过哈希技术在中间增加了一层将数据分配到不同的桶中这一过程用于优化数据库查询效率。具体而言，在查询阶段首先会通过计算query对应的桶编号来确定该区域内可能包含的相关样本集合随后会基于这些样本之间的相似性评估方法如欧氏距离余弦距离等来进行精确匹配并按匹配程度返回结果这一流程往往采用一组或多个哈希函数构成一个索引表其中每个表包含若干个独立的子区域（即"桶"）。为了进一步提高搜索结果的准确性可以在构建索引时采用多表结构但这必然带来一定的时间开销以时间开销为代价能够使整体系统的准确率得到显著提升。
分层法的主要代表算法是E2LSH。
- 哈希编码方案采用哈希码替代原始数据进行存储，在分层结构中, 原始数据仍然需要在第二层用来计算相似度. 而哈希编码方案不需要, 它利用LSH函数将原始数据直接转换为哈希码, 在计算相似度时则采用汉明距离来进行衡量. 将数据转换为哈希码后, 相似度的计算变得极为迅速. 比如, 可以使用64位整数来存储每个哈希码, 并且通过同或操作即可快速得到汉明距离结果. 这种速度令人难以置信, 不由得用拟声词来表达我的惊喜之情, 希望各位读者能够理解这种高效性. 哈什
code编码方案的代表算法包括KLSH、Semantic Hashing和KSH等.
1.3 分层法与哈希码法区别
以我看来，两者的区别在于如下几点：
- 构建高效的哈希函数对分层法具有更高的要求，在该方法中即使分层法的计算精度稍逊于KSH（即KSH胜则胜败则败），但分层法通过后续阶段的数据直接比较来弥补这一不足，在实际应用中总能得到较为理想的相似度结果。
- 从时间复杂度的角度来看，在分层法中时间开销主要集中在桶内样本间的相似度计算上；而在KSH（即KSH胜则胜败则败）中时间开销主要集中在候选样本与查询点之间的汉明距离计算上。相比于其他方法，在处理高维数据时分层法能够较好地平衡各维度的信息。
- 在具体的实现过程中两者的构建方式存在一定的互通性：例如E2LSH（即KSH胜则胜败则败）采用的p-stable LSH函数同样适用于哈希码方法；而KSH等基于树的方法也能够很好地融入到分层法框架中。
- 基于不同需求将它们划分为无监督学习与有监督学习两种类型：无监督学习通常依赖于数据本身的分布特性而无需额外标注信息；有监督学习则需要借助人工标注的数据来进行模型训练与优化。
Unsupervised hashing functions are based on certain probabilistic theories and can achieve local sensitivity, such as E2LSH. Supervised hashing functions are learned from data, such as KSH and Semantic Hashing. Generally speaking, supervised algorithms are more precise than unsupervised ones and are more commonly used in hash coding.
二.常用LSH
2.1 原始LSH****
原始LSH算法通常安排在哈希函数生成之前进行处理，在此过程中首先需要将数据从L1范数下的欧几里得空间映射到Hamming空间。其基本假设是原始数据点基于L1范数的距离表现与基于L2范数的距离表现相当接近，在采用基于向量内积的概率化方法构建Hash函数时，并未直接支持Hamming空间中的度量结构。
Embedding算法如下：
计算所有点及其坐标值中的最大维度值C；
对于数据中的任一元素P，则有P=(x₁,x₂,…,x_d)，其中d表示数据的空间维度数；
对每一条维度数据x_i进行二进制编码转换操作：即生成一个长度固定为C的二进制向量，在该向量中前x_i位取值为1其余位则置零.
随后将各维度处理后的二进制向量依次拼接在一起形成一个完整的特征向量序列.其总长度为d×C.
在实际应用中通常采用以下方法来优化计算效率以减少不必要的中间结果存储需求：
Algorithm of Origin LSH
在Origin LSH中，每个哈希函数的定义如下：
假设输入为一个二进制序列，则其输出对应于该序列中的某个特定位数值。因此，在构造哈希函数族时, 每族中有C^d个不同的哈希函数（共C^d种可能的构造方式）。当将数据映射至目标桶时, 选择k个上述构造的哈希函数来形成一个完整的哈希映射方案。
进一步细化该算法的具体步骤如下：
在区间[0, Cd]中选取L个数值，并将其组合形成桶结构下的哈希函数集合G。
针对给定向量P而言，在经过与集合G中的每个元素相交运算后，则可获得对应的L维哈希码。
由于直接基于上一步骤所得的L维哈希码进行桶标记较为繁琐，
因此需进行第二次处理：第二次处理就是普通的哈希映射操作，
将计算出的最终结果映射为单一实数值。
其中，a是从[0,M-1]中随机抽选的数字。这样，就把一个向量映射到一个桶中了。
作者注：在采用该种嵌入方法时，在这种情况下，海明距离等于曼哈顿距离。那么为何不直接计算曼哈顿距离呢？
其实在这里首先进行了哈希运算，在确定某些位置之后计算两者的汉明相似度，并非通常意义上的曼哈顿距离，并且这样的计算结果在实际应用中并没有实际意义
2.1 LSH based on p-stable distribution
E2LSH遵循p-stable分布，并采用"哈希技术分类"中的分层法作为方法，从而形成了E2LSH算法。
E2LSH中的哈希函数定义如下：
其中, v代表d维原始数据,a是一个服从正态分布的随机变量; w代表宽度值,为了使a·v+b的结果成为一个实数,必须对其进行适当的处理,否则无法实现桶的效果,w是E2LSH算法中最关键的参数之一,如果设置过宽,则会导致所有的数据点都被分配到同一个桶中;反之如果设置过窄则无法达到局部敏感的效果.b则采用均匀分布在[0,w]区间内进行随机生成。
与Origin LSH类似，选取k个上述的哈希函数，组成一个哈希映射。
然而这样会导致计算结果为N_1,N_2,\dots,N_k（其中每个N_i都属于整数域而非仅取0或1两个值），这相当于定义了一个'桶'。如果直接将这些元组作为哈希表的键，则会占用过多内存资源；不仅占用内存较大，并且这种存储方式不利于快速查找所需数据。为了提高存储效率和减少资源消耗，在设计阶段采用了层次化方法：通过结合数组与链表的方式进行组织（如图所示）。
对于所有k元组形式的桶编号，在算法设计中我们通过以下定义的两个函数来计算得到两个数值：其中通过调用该函数得到的结果表示目标数组的位置，并且该数组的实际容量与哈希表的大致规模相当；而另一个函数则返回一个唯一标识符，并将其关联到对应目标位置处所对应的链表元素上。其中r’是在区间[0, prime-1]内通过均匀分布随机数生成器来确定的一个整数值。
经过上述组织后，查询过程如下：给定查询点query q
E2LSH方法存在明显的缺陷：其基于概率模型生成索引编码的方式不够稳定；尽管在增加编码位数时并未见到明显提升效果；此外，在存储空间需求方面表现欠佳
2.3 Hashcode of p-stable distribution
E2LSH可以说是层次化方法利用p-stable分布实现的一种技术。另一种则是通过将数据映射到特定的数值序列来完成哈希编码。
其中
三.疑难点
在将欧氏距离映射至海明空间时？
回答：并未旨在增加冲突概率。实际上所指的与构建过程相关的是扩大两者的差距。然而，在这一过程中两者均有所缩小……或者，在构建过程中……同时扩大两者的差距
2.编辑距离
计算两个序列之间的编辑距离d(x,y)，其公式为d(x,y) = |x| + |y| - 2 × LCS(x,y)，其中LCS代表的是最长公共子序列？该方法尚未经过充分验证。
该研究基于p-稳定分布提出了一种局部敏感哈希方案[C]//Proceedings of the twentieth annual symposia on Computational geometry. ACM, 2004: 253–262.
[3]. Kulis B and Grauman K. Kernel-based LSH [J]. Pattern Analysis & Machine Intelligence, IEEE Transactions, 2012, 34(6): 1092–1104.
Ruslan Salakhutdinov and Geoffrey Hinton. Semantic hashing[J]. Journal of Approximate Reasoning, 2009, 50(7): 969-978.
Liu W 等人. 基于核的监督哈希方法[C]//在《计算机视觉与模式识别》会议（CVPR）上的论文集：在第IEEE计算机视觉与模式识别会议上发表于IEEE期刊上，并在第一页至第十二页的位置
该文献采用基于相似性的搜索方法，在高维空间中通过哈希技术实现高效查询[C]//VLDB会议记录. 论文编号为1999卷第99号的第518至529页.
[7]. http://web.mit.edu/andoni/www/LSH/
[8].