《Locality-Sensitive Hashing Scheme Based on p-Stable Distributions》阅读笔记

       在数据量急速扩张和对搜索速度期望提高的背景下，位置敏感哈希技术（LSH：locality-senstive hashing）应运而生。顾名思义，这种技术就是数据点在哈希之后保持原始数据之间的距离。换一种说法就是，在原始距离中较近的点有较大的可能性被哈希成同一个点，而原始距离中距离较远的点有较大的可能性被哈希成距离很远的数据。

本文对原始的LSH提出了一种改进，即基于一种基于p-stable分布的LSH。

优点：

1.优化了之前的LSH在l_2范数下的运行时间

2.这是第一种高效的在（p<1）l_p范数下的近邻搜索算法

3.该算法可以直接作用于欧拉空间点而不需要嵌入到汉明空间。

4.query的时间复杂度与之前算法相比没有一个很大的常数。

传统位置敏感哈希

p1>p2 ;r1<r2

那么LSH技术是如何解决（R,c）-NN 问题的呢？

1. 定义r1 = R, r2 = cR, 定义相应（r1,r2,p1,p,2）哈希函数族

2. 再函数族中选k个函数构成一个映射到k维函数，新函数族G = {g:s->U_k} 

3.再选一个常数L，从新函数族G中选出L个函数

4.利用这L个函数分别把输入数据映射成L个哈希表

查询步骤：

在查询一个query Q时， 用上述的L个函数分别把Q映射成L个哈希码，然后在相对应的表中找到相应的桶（buket），再从桶中筛选出符号条件的数据点。

其中通过对参数k和L进行恰当的选取，一个正确的哈希算法应保证两个结论：

1.在查询中能找到相似的点

2.控制查询返回的数据点数量。(文中的分析为 3L )

改进的哈希

p-stabel 分布

重要的是

于是文中从p-stable分布中生成一个维度d的向量a，和原始向量v点乘起来就构成了（a.v），几组不同的a分别与v点乘，结果合成一个向量是v向量的低维形式。

哈希算法的改进

仍然是基于位置敏感哈希的最基本思想，如果两个原始数据点在空间上相近，那应该很有很大的概率被哈希到同一个桶中。

点乘的几何意义是投影，文中一个比较形象的说法是，把数据点投影到随机生成的高维直线a上，然后把该直线“切”成响度长度为r的线段，最终投影所在的段就是映射成哈希值。这显然是满足位置敏感的条件的，即保持了数据点在原始空间的距离关系。

形式上就是：

其中，b为[0,r]随机生成的

最后出来的碰撞概率是（f_p（x）是p-stable分布的概率密度函数）：

参考博客 （点击打开链接） 的分析，当哈希码相同时，满足条件||v₁-v₂||_pX=|cX|<r,其中X符合p-stable分布。

碰撞概率证明备注：

1.令||v₁-v₂||_pX=|cX|=t<r, X = t/c, X有概率密度函数f_p():

2.（1-t/r）为直线被分割的宽度大于t的概率

二者相乘得出碰撞概率p(c)

性能分析

与 1/c进行比较

实验分为四部分

首先在数据集构造的时候，特别地了只有极少数点作为Q的近邻点，其他点都在（1+e）R之外。

以下进行了四组实验。

1.

2.

3.

4.

结论

本文提出了一种易于实现的哈希技术改进，并且扩展到了任意的l_p范数空间，p[0,2]