论文阅读笔记: Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing

Posted by CodingCat on February 10, 2015

在很多的场景下,尤其是推荐系统中,关键的一步就是计算元素之间的相似度。在传统意义上,用户的相似度往往是通过离线计算方式生成的,比如user-based, item-based, 这些算法,而随着技术的发展,工业界和学术界都在寻求,把这种离线计算转化为在线计算的途径。这篇来自VLDB的论文就是对这个问题的一种尝试性的解决方案。

所谓的similarity search就是在给定若干物体的情况下,找出物体与物体之间的相似度。这个相似度往往是是一个量化的值。

常见的similarity search是基于物体pair之间的相似度计算,也就是说,加入有N个物体,目标是找出任意一个物体与其余N-1个物体的相似度,这就是所谓的all-pairs similarity search。all-pairs similarity search最大的挑战来源于计算复杂度: 比如一个最直接的方法就是双重循环,两两计算。这种计算方式虽然简单,但是却带来了很多的不便,比如,(x, y)的相似度与(y, x)的相似度是一样的,但是却被计算了两次

所以,一个通常的优化方式是在数据之上建立各种索引,通过索引来匹配物体之间的相似度。例如www 2007的paper, Scaling Up All Pairs Similarity Search, 利用倒排表来动态地查找物体间的相似度 (一边建表,一边输出相似度).

关于LSH

Locality Sensitive Hashing就是一种索引方式。LSH本质上是一种哈希函数,这种哈希函数和我们通常所认识的哈希函数最大的不同是对哈希冲突的态度。通常情况下,即使是相近的原值,我们也希望哈希函数能让他们的哈希函数值尽量离得远一些。但是哈希函数则恰恰相反,在值上相近相同的元素,LSH会把这些元素映射到同一个哈希桶中

具体如下图所示

05B0C052-C546-46FB-BD5F-31CEB9D39006

图中绿色和红色的两个元素在原值空间上相近,在general hashing上通常会将他们map到不同的哈希桶中,而LSH则会把他们放到同一个哈希桶里。

于是查找元素与元素之间的相似度的计算则变成了,把待查找元素的LSH值计算出来,然后输出同一个哈希桶中的函数 (或者设置一个阈值,仅输出在同一个哈希桶里且相似度大于阈值的元素)。LSH本质上是一种近似估计方法,所以,他允许哈希函数的设计拥有一定的误差值。也就是说,给定一个阈值R,与一个待查询的元素p相似度大于R的任何一个元素被作为最相思元素输出的概率要满足1 - alpha, alpha就是被允许的误差度.

那如何来尽量降低alpha的值呢

首先我们需要来分解这个alpha, 产生alpha的原因一共有两种, false negative,也就是说,本来相同的元素,被当成不同的元素散落到不同的哈希桶里; 反之是false positive, 本来不同的元素被当成相同的元素放到同一个哈希桶里

要解决false negative, 我们建立多个哈希表, 每一个元素会在多个哈希表内都被放置,而每一个哈希表对应着一个locality sensitive hashing function, 于是在给定两个相似元素的前提下,只有他们在多个哈希表里都不相同的时候,才会产生false negative

要解决false positive,那么我们就在同一个哈希表内,采用多个哈希函数,每一个哈希函数产生某一个哈希桶的索引的某一位,于是不同的元素只有在所有的哈希函数所产生的每一位都相同的时候才会被映射到同一个哈希桶里

综上所述

我们定义这样一组哈希函数G,每一个哈希函数g(v) 都是由k个子函数hi(v) 组成的,1 <= i <= k。依据G,我们构建L个哈希表,每个哈希表与一个g(v) 绑定,每一个元素经过L次g(v)的计算被映射到L个哈希桶里,在同一个哈希桶中的元素被认为是相似的。 这就是LSH的定义方法。

系统结构

因为LSH已经把比较元素之间的相似度计算通过哈希映射降低了很多,要支持在线的流式计算,最直接的方法就是将LSH扩展成一个分布式计算系统。下图展示的就是这样的一个系统

9488A851-3E35-4980-9B05-8AE15AAD2052

在这个系统中,整个LSH的结构被分散到不同的节点上,每一个节点都维护着部分数据,以及整个LSH的计算函数。如果在这个结构中进行相似元素的查找,意味着一个元素会被广播到所有的节点上并且在其上apply所有的LSH函数,从而得出结论, 在这个节点上到底有没有我们需要的相似的元素。

Coordinator是用来做去重操作的,因为同一对相似元素在不同的哈希表中都可能被映射到同一个哈希桶中,那么我们在查找时就会在不同的哈希表中得到相同的相似元素对,那么Coordinator就是用来把相同的相似元素对去掉的。

至于插入,因为这篇文章的重点就是streaming data,数据源源不断来,我们也要不断去更新LSH索引。至于这部分内容,我们在section 5中重点介绍。

PLSH的过程

建表过程

所谓的建表,就是一个元素是被如何添加到LSH表中的

为了能够更快的讲一个元素通过LSH映射到某一个哈希表的某一个哈希桶中。作者主要采用了两个策略来加速LSH值的计算过程

1) 组合构建每一个哈希表所对应的哈希函数来减少计算量

这个方法并不是作者的原创,而是出自于[1]. 简单说就是,我们在构建与上文中的L个哈希表相关联的哈希函数时,不是对每一个哈希表都从哈希函数族中选择k个函数,而是通过从LSH哈希函数族中选择出k/2的函数,来构建一个u, 并重复这个过程m次, m大约等于L的开方。所以我们一共得到了m个由k/2个哈希函数组成的”更大的哈希函数”

然后对于每一个哈希表Hi,我们构建出一个由任意两个不同的哈希函数u ,串接而成的哈希函数gi

这样,由于m是远小于L的, 所以我们在计算每一个元素的哈希函数值的时候,可以重复利用某一些函数u的计算结果,来减少计算次数

2) 并行计算

2.1) 并行哈希函数计算

这里的并行计算,作者利用了他选取的LSH本身的特质来进行。作者在文中选择了计算两个元素特征向量在高维空间中的角度作为哈希函数。因此,在LSH中每一个最小粒度的哈希函数h的构建过程实际上是在高维空间内,任意选择一个超平面,从而把每一个元素的特征向量与超平面的角度作为他的相似度来看待。

那么基于这样的一个LSH函数,我们就可以构建出两个矩阵: 第一个矩阵的每一行就是一个元素的特征向量,第二个矩阵的每一列则是代表某一个哈希函数的超平面。那么两个矩阵相乘,我们就得到了每一个元素的特征向量与每一个超平面的角度。(角度计算公式:)

6A68F644-3B21-4922-BDC3-3DED28212022

然后再把这些结果串接起来就形成了元素在每一个哈希表中的位置。每一个元素与超平面的计算其实是独立的,因此我们能够在此基础上做并行。

2.2) 并行建表

本文提出的系统在建表的时候也引入了并行计算的特性。对于LSH中L张哈希表中的每一张表,作者首先采用了一个two-pass的算法来用一个连续的数组,而不是散落在内存四面八方的链表来存储元素

具体的做法包括

1) 扫描整张表, 建立一个关于所有哈希桶的元素数量的直方图,
2) 确定所有有元素在其中的哈希桶的偏移位置
3) 扫描每一个哈希桶,从而确定每一个元素的偏移位置

这种结构非常有利于cache的利用。但是仍然存在一个问题,当每一个哈希表对应的哈希函数数量较多时,这个数组会非常长,TLB的大小有限,因此尽管数据结构是一个缓存友好的数据结构,但是其大小还是阻碍了cache去发挥最大的功效。于是作者进一步提出了多次划分的思想来减小数据结构体积,从而更有效的利用cache.

F6024323-F53B-4E9F-AA49-586F8A497B76

如上图所示,作者利用了LSH的哈希函数是由我们在上文中介绍的组合构建哈希函数的方法来建造的条件,将元素,首先通过第一个哈希函数u1来划分,因此,元素首先被划分到m个表中,然后再在每一个m表内部利用第二个哈希函数来划分。

这样划分的好处之一是,我们可以在为不同的哈希函数表添加元素时,重复利用m个哈希函数的计算值来减小运算量;另一个好处就是我们可以并行计算不同的数据的第一层次的划分,并且在第二个层次划分时基于已经获得的第一个层次的划分来并行。

查表过程

在LSH查表过程中,最消耗查询时间的是去重和距离计算。

为什么要去重呢,因为每一个元素会被映射到所有的哈希表中,因此和某一个查询相似的元素可能在不同的哈希表里都出现,那么最终输出的结果就需要先进行去重。

而距离计算的开销(比如计算两个向量的cos值)主要是,在通常的数据中,元素的特征向量都是稀疏的,并且两个元素的特征向量中都有值的部分往往仅仅占某个特征向量有值的长度的一部分。因此一个比较拙劣的方法就是双重循环,对一个特征向量每一个元素在另一个向量里查询,如果有的话就再计算cos值的时候加以考虑,因此这就带来了O(N * M)的复杂度。N, M分别是两个向量的长度

因此作者提出了以下两种方法来分别加速去重和距离计算的过程

去重: 在输出的所有结果的基础上建立一个直方图, 然后去查看那些非0的值。并且使用一个位向量去存储这些直方图,对于有1000万个结果的情况,我们只要一个大小大约为1.25MB的位向量就可以了

距离计算: 距离计算的优化方法和去重差不多,大体就是为每一个向量都设置一个位向量代表他哪些位上有值,通过位操作就可以完成常数复杂度内的”找到两个向量交集”的操作

流式数据的处理

如本论文标题内容所述,这篇论文研究的重点之一是如何应对流式数据的场景。其实我个人觉得这部分,文章做的并不是很好。

在高吞吐的插入操作情景下,文章要解决的第一个问题就是如何做写操作。

为了避免插入操作对原有的LSH结构带来影响(例如,并发竞争,或者对数据的更新), 作者引入了一个delta table, 新插入的数据都被放到这个delta table里,然后当查询时,需要从已存在的LSH table和delta table中同时查询,当delta table的容量已经高于一定的阈值的时候,把delta table和static table合并起来

delta table的实现本质上是L个动态数组,每个动态数组最大容量都是2^k, 动态数组的每一位都对应被映射到同一个哈希桶中的元素。 那么插入的时候就不要像之前介绍的static 部分的一样, 对元素进行两次划分。

E65AA75B-6961-4C2C-A980-66022FA0D85E

为了使得delta table的操作的影响最小化,作者还采用了load batching的方法。至于

本文要解决的第三个问题就是,因为文章是完全利用了内存作为存储空间来存储LSH中的元素,所以容量有限。因此为了拓展容量,就必要要定时或者不定时得把一些老的数据从系统中删除。

本文采用的方法是在插入时,每次都把插入操作限定到某M个节点中,然后当这些节点容量已满时,像滑窗一样,顺序的移动这个窗口,来选定下M个节点来服务写操作。那么当系统满载时,我们就知道前M个节点是存储的最老的数据,于是这些节点上的数据就被擦掉。(个人观点: 这真是一个丑陋不堪的方法啊!!!!!)

本文应该说是把相似度计算做成在线计算的一个尝试。。。但是从系统角度说。。问题很多

[1] A. Andoni and P. Indyk. Efficient algorithms for substring near neighbor problem. In Proceedings of SODA, pages 1203–1212, 2006.