適用于最近鄰檢索的堆疊哈希量化算法.pdf

1、目前，各種類型的信息數據呈爆炸型增長。傳統信息處理技術正面對著前所未有的挑戰(zhàn)。如何在海量高維數據中高效查找目標數據，是計算機領域的熱門問題之一。近似最近鄰檢索是解決該問題的一種方案，它的主要思想是提出新的近似距離度量，檢索在這種度量下和查詢對象距離最近的數據對象。目前，許多近似最近鄰算法陸續(xù)出現，且被應用于多個領域。
　　乘積量化是解決此問題的有效方法之一，具有內存消耗低，查詢效率高等優(yōu)點。不過，乘積量化需建立量化中心的距離查詢表

2、，時間復雜度較高。針對此缺點有人提出了k-means哈希量化，直接把向量數據量化為二進制碼，且盡量保持數據的空間近鄰結構。由于二進制碼漢明距離的計算遠遠快于向量歐氏距離計算，此方法節(jié)省了存儲空間和運行時間。然而它本質上是把一個高維超立方體放在原始空間內做迭代優(yōu)化，若立方體維度較高，優(yōu)化速度過慢，內存消耗也比較大。
　　為此，本文提出了一種新的量化算法——堆疊哈希量化算法。若要提高二進制碼對于原始數據的近似程度，不能僅依靠增大超立方

3、體的維度，可以通過利用多層低維立方體對原始數據進行逐步逼近，本文稱之為堆疊哈希量化。該算法的核心思想為:第一步，在訓練數據集上，用乘積量化將高維訓練集劃分為多個低維訓練集;第二步，對低維子空間進行k-means哈希訓練產生相應碼本;第三步，計算上一步之后的誤差向量，將其作為新的訓練數據進行碼本訓練，得到相應碼本;重復第三步直至達到給定誤差或規(guī)定碼本層數。再利用分層碼本集對數據庫的數據進行編碼，得到多層哈希碼。在線查詢階段，首先利用分層碼