Hamming空間中的快速近鄰檢索算法.pdf

1、近鄰檢索問題是機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)較為基礎(chǔ)的研究問題，其相關(guān)的實(shí)際應(yīng)用問題數(shù)不勝數(shù)，例如相似圖像檢索、基于近鄰檢索的圖像分類問題等。過去的幾年中，近鄰檢索方面的研究層出不窮，近鄰檢索問題的相關(guān)算法大致可以分為五類：線性掃描算法、樹形索引算法、近鄰圖算法、哈希算法以及反向索引算法。
　　線性掃描算法是解決近鄰檢索問題最基本的方法，即通過遍歷每個(gè)數(shù)據(jù)進(jìn)而找到查詢數(shù)據(jù)的近鄰。樹形索引算法利用了樹形數(shù)據(jù)結(jié)構(gòu)劃分空間，并建立索引結(jié)

2、構(gòu)來進(jìn)行近鄰檢索。近鄰圖算法對(duì)數(shù)據(jù)庫中的數(shù)據(jù)建立近鄰圖結(jié)構(gòu)用于輔助近鄰檢索過程。哈希算法通過將數(shù)據(jù)由原始數(shù)據(jù)空間映射到Hamming空間，進(jìn)而將近鄰檢索問題轉(zhuǎn)化為Hamming編碼相關(guān)的問題。反向索引算法通過聚類等方法建立反向索引結(jié)構(gòu)用于提高近鄰檢索的效率。
　　相關(guān)的近似近鄰檢索算法被提出[1]，該方法提出了“橋向量”的概念，其概念和乘積量化[2]中聚類中心的概念比較類似。該算法基于橋向量和增強(qiáng)近鄰圖，提出了“需求驅(qū)動(dòng)的實(shí)時(shí)提取

3、”策略，在線檢索階段采用優(yōu)先級(jí)搜索的方式進(jìn)行近鄰檢索。近些年來，基于二進(jìn)制編碼和二進(jìn)制視覺特征的大規(guī)模圖像檢索方面的研究在計(jì)算機(jī)視覺領(lǐng)域引起了廣泛的關(guān)注。盡管二進(jìn)制編碼以及二進(jìn)制特征可以提高計(jì)算效率，但針對(duì)大規(guī)模數(shù)據(jù)庫通過線性掃描來檢索近鄰的方法依然計(jì)算開銷巨大。在這篇文章中，我們將[1]中的近鄰檢索算法進(jìn)行泛化，將其適用性擴(kuò)展到Hamming空間。該擴(kuò)展算法利用了Hamming空間中的K-平均聚類算法。我們提出的方法和現(xiàn)有的Hammi