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

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

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

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