[發明專利]一種可變長度哈希編碼的高維數據最近鄰查詢方法

有效

• 申請號: 201811298578.4
• 申請日: 2018-11-02
• 公開（公告）號: CN109684518B
• 公開（公告）日: 2021-09-17
• 發明（設計）人: 任艷多;錢江波;孫瑤;胡偉
• 申請（專利權）人: 寧波大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/9032
• 代理公司: 寧波奧圣專利代理有限公司 33226
• 代理人: 程天鵬

1.一種可變長度哈希編碼的高維數據最近鄰查詢方法，其特征在于包括以下步驟：

①獲取包含多個原始高維數據的原始高維數據集并給定查詢點，對原始高維數據集做低維映射，生成由與每個原始高維數據對應的隨機傅里葉特征向量組成的隨機傅里葉特征向量集；

②根據每個隨機傅里葉特征向量的哈希值進行編碼獲得與每個原始高維數據對應的哈希碼，對所有哈希碼中每個哈希碼出現的次數進行統計得到用于表示每個哈希碼出現頻率的編碼頻率，將編碼頻率相同的哈希碼作為一組子數據集得到多組子數據集，并按編碼頻率從高到低的順序對所有子數據集進行排列得到每個子數據集的排序序號，對每組子數據集設置一個與該組子數據集的編碼頻率互為倒數的壓縮比，根據壓縮比對每組子數據集進行壓縮，得到壓縮后的子數據集及壓縮后的子數據集的編碼長度，然后按照壓縮損失及量化損失之和最小的方法對壓縮后的子數據集進行訓練，得到訓練后的子數據集及訓練后的子數據集的哈希編碼；

③將每組訓練后的子數據集通過提取隨機傅里葉特征得到與每組訓練后的子數據集對應的原始編碼，根據原始編碼的編碼長度和原始編碼對應的壓縮比復制每組訓練后的子數據集的哈希編碼，得到每組訓練后的子數據集的哈希編碼的多個復本；

④將每組訓練后的子數據集的原始編碼和每組訓練后的子數據集的哈希編碼的復本串聯得到與每組訓練后的子數據集對應的串聯后的哈希編碼，將所有訓練后的子數據集對應的串聯后的哈希編碼融合組成最終的最近鄰查詢表；

⑤對給定的查詢點提取隨機傅里葉特征向量，將給定的查詢點的隨機傅里葉特征向量映射到與訓練后的子數據集對應的串聯后的哈希編碼的編碼長度一致的隨機傅里葉編碼，將該隨機傅里葉編碼作為查詢點對應的查詢編碼，最后在最終的最近鄰查詢表中查找與查詢點對應的查詢編碼海明距離最近的最近鄰數據集，將該最近鄰數據集作為給定的查詢點的最近鄰查詢結果，完成對給定的查詢點的最近鄰查詢過程。