定向多探頭隨機超平面局部敏感哈希.pdf

1、隨著人類步入大數(shù)據(jù)時代，人們的衣食住行都離不開信息與數(shù)據(jù)。相似性搜索是大數(shù)據(jù)研究的一個重要方向。數(shù)據(jù)的分析與處理往往離不開對高維數(shù)據(jù)的匹配與查找。針對于高維數(shù)據(jù)的大規(guī)模相似性搜索，局部敏感哈希被認(rèn)為是一個行之有效的方法且同時被廣泛的運用到各個領(lǐng)域中。
　　在最近的幾年，許多有關(guān)局部敏感哈希的改進算法相繼被提出。在使用局部敏感哈希時，為了提高搜索的質(zhì)量，往往需要消耗大量的空間來存儲哈希表。為了克服這個缺陷，相關(guān)的研究者提出了基于多探

2、頭的局部敏感哈希。此方法在很大程度上提高了哈希表的利用率，從而節(jié)省了存儲空間。對于多探頭局部敏感哈希，現(xiàn)在最常用的兩類探尋方式分別為步進式多探頭局部敏感哈希與定向多探頭局部敏感哈希。相比于步進式多探頭局部敏感哈希，定向多探頭局部敏感哈希搜索速度更快，所需探頭數(shù)量更少。然而如今定向多探頭探尋方式是基于E2LSH。這意味著它只能適用于歐式距離。
　　對于余弦相似系數(shù)，步進式多探頭局部敏感哈希是唯一可執(zhí)行的多探頭探尋方式。提出一種基于定

3、向多探頭探尋方式的局部敏感哈希用以彌補余弦相似系數(shù)下定向探尋方式的空白。同時給出一套完整的數(shù)學(xué)理論證明作為算法的理論依據(jù)。
　　為了說明該算法的優(yōu)越性，采用了多個公開數(shù)據(jù)集分別對定向多探頭隨機超平面局部敏感哈希與步進式多探頭隨機超平面局部敏感哈希進行了實驗。根據(jù)實驗結(jié)果，前者相比于后者在達到相同的召回率時需消耗更少的探頭與搜索時間。算法相比于原始局部敏感哈希有更高的空間利用率。另外定向探尋方式僅僅改變了探尋順序并沒有改變存儲空間中