文档介绍：Similarity Search in High Dimension via Hashing
LSH算法:
1、算法思想:将高维空间中的元素视为点并赋以坐标值,坐标值为正整数。通过一族哈希函数将空间所有点映射到n个哈希表中,n=||,即每个哈希函数f对应一个哈希表,每个哈希表都存放着空间所有的点。对于给定的查询子q,分别计算、、…、,,i=1,2,…,n 。以所有落入的哈希表中的桶中所有点作为候选集,比较其与q之间的距离,选出距离最近的K个点(K-NNS)。
2、算法步骤
(1)预处理:对于任意一点P,P为d维空间。设={,,…,},将空间P映射到维Hamming空间,映射方法如下:
,
=()()…()
其中()表示个1紧跟C-个0,C表示空间P中任意点坐标的最大值。
这种映射是保距的,即p,qP,=。其中表示定义在空间P上准则下的欧几里得距离,表示定义在空间下的Hamming距离。因此原问题——找出空间P中与查询子q距离最近的K个点——转化为在空间中的-NNS问题。在算法实现中,并没有显式将p转化为,而是用别的计算方法利用了这种转化,使算法易于描述并且实现的时空效率高。下面定义哈希函数的过程中,p代表了原始点的向量形式(即),即不会区分p与。
(2)定义哈希函数族:定义I={1,2,…,},定义正整数,取个I的子集,分别记为,,…,。定义p|I为向量p在坐标集I上的投影,即以坐标集I中每个坐标为位置索引,取向量p对应位置的比特值并将结果串联起来。比如I={1,5,7,8},p =1**********(对应原始点p={2,1,3},d=3,C=4),则p|I=1100。记=p|I,我们将空间P中的所有点利用哈希函数族都存入哈希表的哈希桶中。哈希族的形式如下图所示:
……
……
……
……
表 1
表中有个哈希表,第i个哈希表有个哈希桶,即第i个哈希表将空间P中的点映射到了个不同位置。因此表中共有个哈希桶。
因为哈希桶的数量可能会很大,因此采用第二层哈希,利用标准哈希函数将所有的哈希桶映射到一个大小为M的哈希表中。记该哈希表中的哈希桶最大容量为B,在算法中采取的冲突解决方法是:当一个哈希桶内点的个数超过B时,则新分配一个大小为B的桶并将该新桶连接到原来的桶中,而在实现的过程中,采取了更简单的方法:当一个哈希桶中点的个数超过B时,则不能再有点插入,当有新点分配到该桶中时,该点会被分配到其他未满的哈希桶中。新的哈希表如下表所示:
中逻辑上存储的是表1中的哈希桶,物理上存储的是表1的哈希桶中存储的空间P中的点。
(3)查询操作:对于给定的查询子q,计算,,…,,取出对应哈希桶中所有的点(即满足=的点p的集合)作为候选集。最后在候选集中选出K个距离查询子q最近的K个点。
(4)小问题
1)集合I的子集,,…,,对于j=1,2,…,,由从集合{1,2,…, }随机的均匀的可放回的选取k个元素组成。最好的k要使距离近的元素映射到同一个桶中,距离远的元素映射到不同的桶中。
2)前面提到,实际实现中不必显式的将d维空间P中的点p映射到维Hamming空间的向量,而是使用其他的方法隐式的进行。方法是这样的:记d维空间P中的点p映射到维Hamming空间的向量为,坐标集I{1