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

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

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

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

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