如何减少Locality Sensitive Hashing系统中的哈希表的数量

Posted by CodingCat on February 26, 2015

最近读了 Multi-Probe LSH: Efficient Indexing for HighDimensional Similarity Search [1] 这篇文章,觉得还是很有意思的,做一个简短的总结。

对于LSH 已经在(http://codingcat.me/blog/2015/02/10/streaming-similarity-search-over-one-billion-tweets-using-parallel-locality-sensitive-hashing/) 给出了介绍

在那篇论文里,作者使用了700个哈希表。所以这突出了LSH的一个问题,为了在FALSE POSITIVE和FALSE NEGATIVE之间有足够的tuning空间,必须使用大量的哈希表。这种大量的哈希表的使用带来了两方面的开销,一个是对于系统存储空间的消耗,还有一个是处理查询时开销 (每一个查询要被哈希700次(其实不止, 因为每一个哈希表对应的哈希函数也是多个哈希函数串接而成)然后在700个哈希表里查询)。

Multi-Probe基于的理论是,根据LSH的特质,那么即使不是在同一个哈希桶里的元素,如果他们的哈希桶位置相邻,他们一定也是有很大的相似可能性的。所以,我们在有很少的哈希表的情况下,要做的就是去找临近的哈希桶里的函数。

如何做呢?简单说,就是在每一个查询的哈希值(就是哈希桶的索引)的基础上,施加一个扰动向量,这个扰动向量和原哈希值的值就是临近哈希桶的索引。

所以,我们要做的就是产生这个扰动向量。类似多哈希表的情况,我们其实要产生的是一个扰动向量的序列,这样才能保证我们在false positive和false negative之间有较大的tuning 空间(序列长度).

我们用

ABAA45C3-27CC-494F-8FE3-FC09FE572838

来表示一个扰动向量,M是哈希表对应的哈希函数的个数.所以扰动向量存在的意义就是去改变某一个查询的某一个哈希函数的值,从而使它的哈希桶位置发生偏移。根据LSH的特性 (具体的概率分布见原文), 一个近似的元素是否存在于一个哈希桶中的概率是和扰动向量加上原先向量的值成比例的,值越小,存在近似元素的可能性越高。于是我们就可以用下面这样一个指标来确定一个扰动向量产生近似元素的可能性

5F8AA17C-0ACE-4541-AFB8-78D6A2A603C6

其中x是值查询元素到由扰动向量的第i位产生的哈希桶的距离(拗口。。。慢慢理解吧,不然一扯一大段)。这个距离的衡量又是由这个方法中采用的哈希函数来决定的

AA0A7943-CE0B-4222-8AAE-23269B682B8D

这个哈希函数的本质就是把一个向量,在他的维数空间里映射到一个直线上,并且以W为区间长度分隔成等份,哈希函数的值就是向量最终被映射到的区间的ID。而这个区间ID 就是哈希桶的ID。

因此我们会发现,近似元素到底在当前元素所在区间的哪一个临近区间里是由差选向量本身 (影响了哈希值) 和 偏移量决定的。所以我们才得到了score那个公式。

下面就是选取序列的算法了

8AE5CD1A-7F1C-41FC-AF3A-07CE8E9D3FDA

其中A是与扰动向量对应的一个集合,集合中的每一个元素对应了扰动向量的每一个不为0的位,叫做扰动集合。算法通过维护一个最小堆来选择出T个扰动集合,从而产生得分最低的T个扰动向量(即最可能找到近似元素的T个向量)。

讨论到这里,算法的最大的弱点是维护min-heap的复杂度太高。要知道,这是对每一个查询都维护一个heap。所以作者又提出了使用扰动向量每一位, 下文中的zi,的期望值来估计最终的扰动向量值。从而,所有的扰动向量都是实现计算好的,不需要为每个查询单独产生。

这一部分就直接上原文了,实在没什么好解释的

10AC2A51-B1F5-457F-9470-7B22AF7D6C86