位置敏感哈希算法的性能分析研究.pdf

1、隨著大數(shù)據(jù)時(shí)代的來(lái)臨，在諸如圖像與多媒體數(shù)據(jù)庫(kù)、地理信息系統(tǒng)、數(shù)據(jù)挖掘與分析系統(tǒng)等海量數(shù)據(jù)應(yīng)用系統(tǒng)中，都需要在大數(shù)據(jù)集中進(jìn)行最近鄰查找，即查找出與給定查詢對(duì)象最為相似的一個(gè)或一組對(duì)象。最近鄰查找問(wèn)題在低維空間已經(jīng)有較為有效的解決方案，而在高維數(shù)據(jù)空間，由于“維度災(zāi)難”的存在使得最近鄰查找問(wèn)題變得非常困難，目前解決這一問(wèn)題最有效的技術(shù)是建立高維索引。
　　現(xiàn)有高維索引主要分為樹(shù)結(jié)構(gòu)索引和基于哈希的索引兩類(lèi)。樹(shù)結(jié)構(gòu)索引技術(shù)通過(guò)對(duì)空間進(jìn)

2、行劃分建立樹(shù)形的輔助查詢結(jié)構(gòu)，在數(shù)據(jù)維度較低時(shí)，效果較好。當(dāng)維度超過(guò)數(shù)十維后，樹(shù)結(jié)構(gòu)索引容易產(chǎn)生索引空間重疊問(wèn)題，導(dǎo)致索引占用空間大且時(shí)間效率低。在基于哈希的索引技術(shù)中，利用查詢對(duì)象哈希函數(shù)值可以在次線性時(shí)間內(nèi)查找到與其較為相似對(duì)象，因而得到廣泛的研究和應(yīng)用。
　　在廣泛閱讀國(guó)內(nèi)外參考文獻(xiàn)的基礎(chǔ)上，本文對(duì)位置敏感哈希算法進(jìn)行了系統(tǒng)的研究。在研究中，我們發(fā)現(xiàn)位置敏感哈希理論與基于該理論的算法實(shí)現(xiàn)有著本質(zhì)差別，而這一差別導(dǎo)致應(yīng)用傳統(tǒng)性

3、能分析方法所得到的分析結(jié)論是不正確的。
　　為此，本文從位置敏感哈希算法性能分析入手開(kāi)展研究工作，論文工作包括:
　　(1)闡述了位置敏感哈希理論和基于該理論的算法實(shí)現(xiàn)間的本質(zhì)區(qū)別。使用真實(shí)數(shù)據(jù)集對(duì)位置敏感哈希算法的理論性能與實(shí)際性能進(jìn)行對(duì)比分析，在實(shí)驗(yàn)上驗(yàn)證了二者是完全不同的。
　　(2)傳統(tǒng)位置敏感哈希算法性能分析所基于的前提在實(shí)際應(yīng)用中并不存在，因而會(huì)導(dǎo)致理論分析結(jié)果與實(shí)際性能不符合。在實(shí)驗(yàn)中表現(xiàn)為位置敏感哈希算

4、法的召回率會(huì)在理論值附近上下波動(dòng)，而非精確相等。為此，我們提出了新的位置敏感哈希算法性能分析模型，該模型能精確地預(yù)測(cè)算法的實(shí)際性能。
　　(3)為了驗(yàn)證新模型的有效性，在E2LSH代碼的基礎(chǔ)上，完成了基于位置敏感哈希理論的兩種算法實(shí)現(xiàn)——LSHN和LSHC。使用Mnist、Color、Audio等高維數(shù)據(jù)集，通過(guò)實(shí)驗(yàn)比較了LSHN和LSHC的召回率和碰撞率。實(shí)驗(yàn)結(jié)果表明，傳統(tǒng)性能分析方法得到的結(jié)果與實(shí)際算法性能有不小的差距，而本文