基于LSH的大數(shù)據(jù)近鄰查詢技術(shù)研究.pdf

1、近鄰查詢是在給定數(shù)據(jù)集中返回與查詢對象距離最近的數(shù)據(jù)對象。作為計算機科學(xué)的一個基礎(chǔ)問題，近鄰查詢被廣泛應(yīng)用在多個計算機領(lǐng)域，包括數(shù)據(jù)挖掘、機器學(xué)習(xí)以及信息檢索等。
　　如今人類社會已經(jīng)步入大數(shù)據(jù)時代，全球以電子方式存儲的數(shù)據(jù)量呈爆炸性增長，我們所面臨的挑戰(zhàn)已經(jīng)不是缺少足夠大的數(shù)據(jù)量，而是如何發(fā)現(xiàn)那些能夠滿足自己需求的、有價值的信息。這些數(shù)據(jù)信息變得越來越復(fù)雜，很多情況下以高維方式存儲，傳統(tǒng)低維數(shù)據(jù)空間表現(xiàn)良好的算法，在處理高維數(shù)據(jù)

2、時，算法時間效率會下降到接近線性查找的程度，也就是所謂的“維度災(zāi)難”。維度災(zāi)難和數(shù)據(jù)規(guī)模兩個問題疊加，使得近鄰查詢問題變得非常困難。
　　在實際很多的應(yīng)用場景中，近似結(jié)果也能很好地滿足需求，于是有研究人員提出以近似近鄰查詢問題來解決準確近鄰查詢問題。局部敏感哈希（Locality Sensitive Hashing）及其變體是解決高維數(shù)據(jù)近似近鄰查詢問題的有效方法，它有堅實的理論基礎(chǔ)，在高維空間中表現(xiàn)優(yōu)異。但是大多數(shù)現(xiàn)有的LSH相

3、關(guān)研究成果是集中式處理數(shù)據(jù)，在處理大規(guī)模數(shù)據(jù)時的性能依然有待提高，尤其是時間效率和可伸縮性。因此，高維大數(shù)據(jù)的近似查詢問題成為一個充滿挑戰(zhàn)和迫切的任務(wù)。
　　在分析 LSH算法以及 Hadoop分布式系統(tǒng)的基礎(chǔ)上，本文研究并改進了現(xiàn)有 LSH的算法結(jié)構(gòu)，提出并實現(xiàn)了高維大數(shù)據(jù)近似近鄰查詢問題的解決方案。具體包括：
　　1、分析了傳統(tǒng) LSH方案的不足之處，拓展 AND-OR結(jié)構(gòu)，提出了沖突計數(shù)排序（C2 SLSH）算法并進行

4、嚴謹?shù)睦碚摲治龊蛯嶒烌炞C，在保證高正確率的情況下，可通過索引而不用比較原始數(shù)據(jù)直接實現(xiàn)高維大數(shù)據(jù) k近鄰搜索。該算法具有穩(wěn)定的可擴展性和較好的時間效率，可以作為高維大數(shù)據(jù)處理的一種方法。
　　2、全 k近鄰查詢（AkNN查詢），是 k近鄰查詢的一個變型，旨在一個查詢過程中為給定數(shù)據(jù)集中的每個對象確定 k個最近鄰。本文使用行條化思想結(jié)合 p-satble LSH算法將高維數(shù)據(jù)對象降維，然后結(jié)合空間填充曲線 Z-order的優(yōu)良特性，