[發明專利]一種高維數據的近似最近鄰檢索方法及檢索系統

在審

• 申請號: 201610045628.2
• 申請日: 2016-01-22
• 公開（公告）號: CN105550368A
• 公開（公告）日: 2016-05-04
• 發明（設計）人: 蔡登;金仲明;萬信逸;付聰
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 劉靜靜

技術領域

本發明涉及數據檢索技術領域，具體涉及一種高維數據的近似最近鄰 檢索方法及檢索系統。

背景技術

近年來，最近鄰檢索技術在計算機視覺、文本和圖像檢索、數據聚類 等需要處理大規模高維數據的領域中扮演著十分重要的角色。最近鄰檢索 討論的對象是大規模高維數據點，要求能快速地在這些數據點中找到距離 某個檢索點最近的若干數據點。

最近鄰檢索的最基本方法是線性掃描所有數據點與檢索點的距離，并 最終返回其中距離檢索點最近的若干數據點。面對大規模高維數據，每一 次計算兩個數據點之間的原始度量都是非常耗費計算能力的過程，因而線 性掃描的方法是十分低效、不切實際的。為了提高最近鄰檢索的效率，學 者們提出了一些近似最近鄰檢索方法，這些檢索方法的基本思路是通過犧 牲一定精度，來提高檢索效率。

常見的近似最近鄰檢索方法主要包括如下兩類：

1)基于樹結構的方法。首先對所有數據點進行分層次的劃分，然后在 檢索時，從最高層的劃分節點開始到最底層的劃分節點進行比較和剪枝。 經典的樹結構有：KD樹、R樹和層次化Kmeans樹等。

2)基于哈希的方法。首先用數據點來學習哈希函數，然后應用這些哈 希函數將所有數據點編碼成哈希編碼來替代表示原來的高維數據內容，最 后在最近鄰檢索時比較檢索點和數據點在編碼后的哈希編碼之間的海明 距離，選擇其中海明距離最近的若干個點作為最終的最近鄰點。為了進一 步加速檢索，可以使用哈希表來存儲所有數據點；另一方面，為了提高檢 索精度，使用海明距離來選擇最近鄰點的候選點，然后再比較候選點和檢 索點之間的實際距離，并返回實際距離最近的若干候選點作為最近鄰結果。

由于實際應用中數據的復雜性，在處理許多高維數據時，現有方法難 以獲得良好的效果?；跇浣Y構的方法對高維數據進行最近鄰檢索時，面 臨著維度災難帶來的一些問題。而基于哈希的方法，若哈希編碼較短，存 在著精度低的問題；若哈希編碼較長，則無法使用哈希表來剪枝檢索。

發明內容

本發明提供了一種高維數據的近似最近鄰檢索方法，能夠提高對高維 數據進行最近鄰檢索時的效率。

一種高維數據的近似最近鄰檢索方法，包括：

步驟1，采用初始化檢索方法對高維數據庫點集，建立初始化索引， 并建立所述高維數據庫點集的最近鄰表；

步驟2，根據初始化索引，獲得待檢索數據點在所述高維數據庫點集 中的若干個最鄰近點，若干個最鄰近點構成初始候選點集；

步驟3，構造臨時點集，針對初始候選點集中的每個數據點，在最近 鄰表中查詢該數據點的若干個近鄰點，并將查到的各近鄰點以及初始候選 點添加至臨時點集中；

步驟4，計算臨時點集中所有數據點與待檢索數據點的距離，將距離 最小的若干個數據點作為新的候選點集；

步驟5，將新的候選點集作為初始候選點集；

步驟6，重復步驟3～步驟5，直至候選點集中的數據點不再更新或者迭 代次數達到預定值，輸出候選點集中距離待檢索數據點最近的若干數據點 作為近似最近鄰數據點進行。

步驟1中的初始化檢索方法可以采用現有技術中的任意一種，作為優 選，所述初始化檢索方法為層次化Kmeans樹算法、隨機化KD樹算法、局 部敏感哈希算法、哈希算法中的一種。

本發明中輸入為待檢索點和高維數據庫點集，輸出為待檢索數據點在 高維數據庫點集中最鄰近點。

本發明還提供了一種高維數據的近似最近鄰檢索系統，包括：

初始化模塊，用于采用初始化檢索方法對高維數據庫點集，建立初始 化索引，并建立所述高維數據庫點集的最近鄰表；

初始化檢索模塊，用于根據初始化索引，獲得待檢索數據點在所述高 維數據庫點集中的若干個最鄰近點，若干個最鄰近點構成初始候選點集；

臨時點集更新模塊，用于構造臨時點集，針對初始候選點集中的每個 數據點，在最近鄰表中查詢該數據點的若干個近鄰點，并將查到的各近鄰 點添加至臨時點集中；

候選點集更新模塊，用于計算臨時點集中所有數據點與待檢索數據點 的距離，將距離最小的若干個數據點作為新的候選點集；