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

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

2、構來進行近鄰檢索。近鄰圖算法對數據庫中的數據建立近鄰圖結構用于輔助近鄰檢索過程。哈希算法通過將數據由原始數據空間映射到Hamming空間，進而將近鄰檢索問題轉化為Hamming編碼相關的問題。反向索引算法通過聚類等方法建立反向索引結構用于提高近鄰檢索的效率。
　　相關的近似近鄰檢索算法被提出[1]，該方法提出了“橋向量”的概念，其概念和乘積量化[2]中聚類中心的概念比較類似。該算法基于橋向量和增強近鄰圖，提出了“需求驅動的實時提取

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