近似最近鄰算法中的高效索引結構研究.pdf

1、在計算機以及網(wǎng)絡技術高速發(fā)展的今天，互聯(lián)網(wǎng)已經(jīng)漸漸走進了我們的生活當中，面對著互聯(lián)網(wǎng)中眼花繚亂的圖像數(shù)據(jù)，人們如何在其中找到自己所需要的內容成為一個急需解決的問題。因此，圖像檢索技術應運而生。在當今的圖片存儲技術當中，一張圖片的維度高達成百甚至上千維，此時我們傳統(tǒng)的檢索會退化成順序遍歷查找。為了克服這個問題，學者們提出了近似最近鄰(ApproximateNearest Neighbors，ANN)檢索方法，同時通過構建高維數(shù)據(jù)索引來提高

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

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