原始LSH算法详解

Similarity Search in High Dimension via Hashing LSH 算法： 1、算法思想：将高维空间中的元素视为点并赋以坐标值，坐标值为正整数。通过一族哈希函数将空间所有点映射到n 个哈希表i 中，n=||，即每个哈希函数f对应一个哈希表，每个哈希表都存放着空间所有的点。对于给定的查询子q，分别计算1 ( )f q 、2 ( )fq 、…、( )nfq ，if ，i=1,2,…,n 。以所有( )if q 落入的哈希表i 中的桶中所有点作为候选集，比较其与q 之间的距离，选出距离最近的K 个点（K-NNS）。 2、算法步骤 （1）预处理：对于任意一点pP，P 为d 维空间。设p={1x ,2x ,…,dx }，将空间P 映射到d维Hamming 空间d ，映射方法如下： Ppp， p =cUnary (1x )cUnary (2x )…cUnary (dx ) 其中cUnary (ix )表示ix 个1 紧跟C-ix 个0，C 表示空间P 中任意点 p坐标的最大值。 这种映射是保距的，即p,qP，1 ( , )dp q =( , )Hdp q 。其中1d 表示定义在空间P 上1l 准则下的欧几里得距离，Hd表示定义在d空间下的Hamming 距离。因此原问题——找出空间P 中与查询子q 距离最近的K 个点——转化为在d 空间中的-NNS 问题。在算法实现中，并没有显式将p 转化为p ，而是用别的计算方法利用了这种转化，使算法易于描述并且实现的时空效率高。下面定义哈希函数的过程中，p 代表了原始点的向量形式（即p ），即不会区分p 与p 。 （2）定义哈希函数族：定义I={1,2, …,d},定义正整数l ，取l 个I 的子集，分别记为1I ，2I ，…，lI 。定义 p|I 为向量 p 在坐标集 I 上的投影，即以坐标集 I 中每个坐标为位置索引，取向量 p 对应位置的比特值并将结果串联起来。比如 I={1,5,7,8}，p =110010001110（对应原始点 p={2,1,3}，d=3,C=4），则 p|I=1100。记( )jgp =p|I，我们将空间 P 中的所有点利用哈希函数族( )jgp 都存入哈希表的哈希桶中。哈希族的形式如下图所示： 1T 11( )|gI 11()igp 12()igp …… 11()k igp 2T 22( )|gI 21()igp 22()igp …… 22()k igp 3T 33( )|gI 31()igp 32()igp …… 33()k igp lT ( )|llgI 1()ligp 2()ligp …… ()llk igp 表 1 表中有l 个哈希表，第 i 个哈希表有ik 个哈希桶，即第 i 个哈希表将空间 P 中的点映射到了ik 个不同位置。因此表中共有1liik个哈希桶。...