论文部分内容阅读
随着人类步入大数据时代,人们的衣食住行都离不开信息与数据。相似性搜索是大数据研究的一个重要方向。数据的分析与处理往往离不开对高维数据的匹配与查找。针对于高维数据的大规模相似性搜索,局部敏感哈希被认为是一个行之有效的方法且同时被广泛的运用到各个领域中。在最近的几年,许多有关局部敏感哈希的改进算法相继被提出。在使用局部敏感哈希时,为了提高搜索的质量,往往需要消耗大量的空间来存储哈希表。为了克服这个缺陷,相关的研究者提出了基于多探头的局部敏感哈希。此方法在很大程度上提高了哈希表的利用率,从而节省了存储空间。对于多探头局部敏感哈希,现在最常用的两类探寻方式分别为步进式多探头局部敏感哈希与定向多探头局部敏感哈希。相比于步进式多探头局部敏感哈希,定向多探头局部敏感哈希搜索速度更快,所需探头数量更少。然而如今定向多探头探寻方式是基于E2LSH。这意味着它只能适用于欧式距离。对于余弦相似系数,步进式多探头局部敏感哈希是唯一可执行的多探头探寻方式。提出一种基于定向多探头探寻方式的局部敏感哈希用以弥补余弦相似系数下定向探寻方式的空白。同时给出一套完整的数学理论证明作为算法的理论依据。为了说明该算法的优越性,采用了多个公开数据集分别对定向多探头随机超平面局部敏感哈希与步进式多探头随机超平面局部敏感哈希进行了实验。根据实验结果,前者相比于后者在达到相同的召回率时需消耗更少的探头与搜索时间。算法相比于原始局部敏感哈希有更高的空间利用率。另外定向探寻方式仅仅改变了探寻顺序并没有改变存储空间中哈希表的数据结构。这意味着该算法与现有数据结构并未发生冲突,可以直接被使用于现有的局部敏感哈希算法中。从而在减少了空间消耗的同时也保证了搜索的速度。