一种常见的用于处理高维向量的索引办法。与其它基于Tree的数据结构，如KD-Tree，SR-Tree相比，它较好地克服了Curse of Dimension，能够将KNN的时间复杂度缩减到sub-linear。LSH多被用于文本、多媒体的相似性判断。
LSH是一种概率方法，采用过滤-验证的框架（Filter-and-Refineframwork）.在过滤阶段，LSH利用哈希技术把非相似、不可能成为结果的数据对象过滤掉，过滤之后的数据对象作为候选集，使得相似的数据对象过滤掉，进而在候选集合上进行实际的距离或者相似性度量计算。由于在过滤阶段非相似的数据对象大部分被过滤掉，候选集合的大小必定会远小于原始数据集，因而极大地缩短了查询计算时间，提高了效率。
哈希桶（HashBucket）：哈希表中同一个位置可能存有多个元素，以应对哈希冲突问题，这样，哈希表中的每个位置表示一个哈希桶。
e-NNS问题：对于一个查询子q，返回空间的点p，使得d(q,p)<=(1+e)d(q,P)，d(q,p)表示查询子与空间中点p的距离，d(q,P)表示查询子距空间点集P中最近点之间的距离。
算法思想：定义一系列Hash函数h1,h2,…hn，随机选取其中的k个函数组成函数g(x),设选的是h1到hk，则g(x)=(h1(x),h2(x),…hk(x)),这样选取L个的g函数，g1(x),g2(x),…gl(x)，每个函数对应一个哈希表，对于原始空间中的每一个点p，通过每个g函数分别映射到L到哈希桶中。这样，每个点都会在L个哈希表的某个哈希桶中出现。查询时，给定了查询子q，利用L个g函数同样对q进行映射，将与q落在同一个哈希桶中的点作为候选结果集，计算q与候选结果集中的点之间的距离，并从中选出1个或K个距离最近的点
简单说，将原始的点集按距离分成不同的类，查询与q距离较近的点集时，只需比较和q在同一类中的点集，而不需要比较全部点集，从而节省了搜索时间。
LSH函数构建过程
d维海明空间
例如点p(p1,p2,…,pd),q(q1,q2,…,qd),
令r1=r，r2=(1+e)r
哈希组H{h1,…,hd}，hi(p)=pi,是以(r,(1+e)r,1-r/d,1-(1+e)r/d)为参数的LSH函数组
G=(g1,g2,…,gk),gi(p)=(hi1(p),hi2(p),…,hil(p)),hi1(p)=pi1
gi(p)，从二进制中随机选取l个不重复位形成新的二进制串。
il，从{1,2,…,d}中随机选取l个不重复整数
函数组G也是一个（r,(+e)r,P1,P2）为参的LSH函数组
p-stable LSH算法，不需要将原始空间嵌入到Hamming 空间中，可以直接在欧几里得空间下进行局部敏感哈希运算。