近似最近鄰算法中的高效索引結(jié)構(gòu)研究.pdf

1、在計(jì)算機(jī)以及網(wǎng)絡(luò)技術(shù)高速發(fā)展的今天，互聯(lián)網(wǎng)已經(jīng)漸漸走進(jìn)了我們的生活當(dāng)中，面對(duì)著互聯(lián)網(wǎng)中眼花繚亂的圖像數(shù)據(jù)，人們?nèi)绾卧谄渲姓业阶约核枰膬?nèi)容成為一個(gè)急需解決的問(wèn)題。因此，圖像檢索技術(shù)應(yīng)運(yùn)而生。在當(dāng)今的圖片存儲(chǔ)技術(shù)當(dāng)中，一張圖片的維度高達(dá)成百甚至上千維，此時(shí)我們傳統(tǒng)的檢索會(huì)退化成順序遍歷查找。為了克服這個(gè)問(wèn)題，學(xué)者們提出了近似最近鄰(ApproximateNearest Neighbors，ANN)檢索方法，同時(shí)通過(guò)構(gòu)建高維數(shù)據(jù)索引來(lái)提高

2、圖像檢索的效率。局部敏感哈希(Locality Sensitive Hashing，LSH)和它的變體是解決在高維空間中近似最近鄰查詢問(wèn)題的著名且有效的方法。傳統(tǒng)的局部敏感哈希算法采用的是由幾個(gè)LSH函數(shù)捆綁而成的“靜態(tài)”組合哈希函數(shù)，并建立該組合哈希函數(shù)所對(duì)應(yīng)的哈希表。
　　然而，局部敏感哈希算法存在以下缺點(diǎn):當(dāng)我們對(duì)候選對(duì)象進(jìn)行訪問(wèn)的時(shí)候，需要進(jìn)行大量的隨機(jī)I/O訪問(wèn)操作。即，為了保證返回結(jié)果的精度，會(huì)有大量的數(shù)據(jù)對(duì)象被匹配，

3、這就會(huì)產(chǎn)生大量的I/O開(kāi)銷(xiāo)。而另一個(gè)方面，為了在映射空間可以反映數(shù)據(jù)點(diǎn)的狀態(tài)，我們可以使用漢明距離來(lái)度量距離，但是這樣會(huì)破壞原始特征空間中的鄰域結(jié)構(gòu)，違背了局部敏感哈希的基本目標(biāo)。
　　為了解決上述問(wèn)題，本文提出了一個(gè)新的方法，ManhattanSort-LSH(MS-LSH)。我們利用曼哈頓理論度量數(shù)據(jù)點(diǎn)對(duì)應(yīng)的復(fù)合哈希值之間的距離，進(jìn)而建立索引結(jié)構(gòu)。首先，為了不破壞原始特征空間的結(jié)構(gòu)，我們提出了曼哈頓距離(ManhattanDi