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

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

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

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

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