基于位置敏感哈希的近似kNN查詢算法研究.pdf

1、近年來(lái)，隨著互聯(lián)網(wǎng)技術(shù)和網(wǎng)絡(luò)信息檢索技術(shù)的不斷發(fā)展，尤其許多應(yīng)用面臨數(shù)據(jù)量呈幾何級(jí)快速增長(zhǎng)，并且數(shù)據(jù)維度也逐漸變高。那么，如何高效地處理海量高維數(shù)據(jù)的k近鄰(k-NearestNeighbors，kNN)查詢問(wèn)題已經(jīng)成為當(dāng)前的一個(gè)重要研究課題。由于“維度災(zāi)難”的出現(xiàn)，基于R-tree及其變種索引結(jié)構(gòu)已經(jīng)不能夠滿足用戶的需求，算法效率表現(xiàn)出比暴力查詢方法更差的性能。
　　位置敏感哈希（LocalitySensitiveHashing

2、，LSH）是最受歡迎且適合于解決處理高維數(shù)據(jù)空間下的近似kNN查詢問(wèn)題。然而，該方法的缺點(diǎn)在于為了保證較高的查詢質(zhì)量需要構(gòu)建許多哈希表，導(dǎo)致存儲(chǔ)代價(jià)較高以及查詢效率低下;此外，隨著處理數(shù)據(jù)量規(guī)模的不斷增大以及MapReduce編程模型的廣泛使用，傳統(tǒng)單機(jī)上的查詢算法已經(jīng)不具備處理海量數(shù)據(jù)的能力，查詢效率、索引代價(jià)等各方面都存在很大的提升空間。為了解決上述存在的問(wèn)題，本文針對(duì)現(xiàn)有基于LSH的近似kNN查詢算法進(jìn)行了深入的研究，主要做了以下

3、相關(guān)工作:
　　(1)針對(duì)現(xiàn)有LSH相關(guān)算法索引存儲(chǔ)代價(jià)高以及查詢效率低下等問(wèn)題，本文提出了一種新的二級(jí)混合索引結(jié)構(gòu)LSRP-tree，它先利用RP-tree將整個(gè)數(shù)據(jù)集劃分成多個(gè)子聚類，然后再對(duì)每一個(gè)子聚類構(gòu)建基于LSH的哈希表。基于該索引結(jié)構(gòu)，充分利用LSH哈希函數(shù)碰撞的特點(diǎn)，還分別設(shè)計(jì)了兩種不同的CCP和CCF近似查詢算法，有效地完成了高維數(shù)據(jù)空間下的近似查詢操作。與LSB-tree/LSB-forest方法相比，本文算法在

4、查詢效率、查詢質(zhì)量以及空間代價(jià)方面均有很明顯的提高。
　　(2)為了解決大規(guī)模數(shù)據(jù)處理能力不足的問(wèn)題，文中在分析位置敏感哈希算法以及MapReduce編程機(jī)制的基礎(chǔ)上，利用當(dāng)前非常流行的MapReduce編程模型，結(jié)合MapReduce機(jī)制本身的特點(diǎn)，研究了基于LSH的近似kNN查詢算法，設(shè)計(jì)了一種新的分布式索引結(jié)構(gòu)，并且提出了相應(yīng)的查詢方法。該方法可以有效地解決海量數(shù)據(jù)環(huán)境下的近似kNN查詢問(wèn)題。最后在真實(shí)以及人工數(shù)據(jù)集上進(jìn)行大