[發明專利]基于區域分級航線圖算法的數據檢索方法

有效

• 申請號: 202011558738.1
• 申請日: 2020-12-25
• 公開（公告）號: CN112286942B
• 公開（公告）日: 2021-04-09
• 發明（設計）人: 溫序銘;楊瀚
• 申請（專利權）人: 成都索貝數碼科技股份有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/24;G06F16/2453;G06K9/62
• 代理公司: 成都九鼎天元知識產權代理有限公司 51214
• 代理人: 賈年龍

本發明公開了一種基于區域分級航線圖算法的數據檢索方法，包括步驟：通過迭代聚類算法對整個區間的數據進行區域劃分，并主動選擇分級航線圖算法HNRG中每級的區域大小和整個航線圖的分級數來初始化區域分級航線圖，并用于構建索引；利用構建的索引來檢索查詢數據的近似最近鄰等；本發明適用于高維大數據的快速近似檢索，實現了快速、精確匹配高維數據，提高了數據檢索效率。

技術領域

本發明涉及數據檢索領域，更為具體的，涉及一種基于區域分級航線圖算法的數據檢索方法。

背景技術

隨著互聯網，多媒體，以及各種網絡應用的高速發展，各種各樣的數據影響著、服務著我們的生活，數據規模急速增長，在多個領域以及大企業內，數據規模已經積累到TB、PB甚至EB級別。數據在爆炸式增長的同時出現了一些新的特點，其中最突出的特征是數據的高維化。為了使數據能夠更好的表達和記錄人們生活的方方面面，許多領域的數據維數動輒成百上千。傳統的數據檢索方法想精確匹配高維數據難上加難，很難滿足時間上的需求，最基本的數據檢索過程效率低下，使得自然語言處理，機器學習等上層算法難以進行。為了解決此難題，學者們提出了很多的檢索結構，各種樹形結構如kd-tree，X-tree，M-tree等被提出。樹形結構在數據維度低時效果優秀，但隨著數據維數的增加，算法效率急劇下降，檢索時間復雜度指數級上升，甚至不及線性掃描的速度，這就是許多檢索算法無法克服的“維度災難”（又稱“維度詛咒”）問題。

又因為在工業上，多數應用并不需要完全精確的結果，學者們提出了近似最近鄰檢索（ANNS）的概念，允許查到結果與最優解存在一定的誤差，以此來滿足算法在實際應用中對查詢效率的要求。目前，性能優秀的近似最近鄰檢索算法有很多，如annoy、panns、kgraph、faiss等算法和庫都得到了廣泛的應用。其中，分層通航小世界圖（HNSW）算法被認為是近似最近鄰檢索算法中性能最優的算法，此算法是通航小世界圖（NSW）的升級版，通過分層來實現由“粗”到“細”進行搜索，實現了對數級時間復雜度。然而，在實際應用中分層通航小世界圖算法有兩個明顯的缺點：

（1）因為分層通航小世界圖算法在構圖階段的層數選擇依靠隨機數來決定，所以此算法在構圖階段具有較大的隨機性，導致此算法的性能有一定的波動。

（2）分層通航小世界圖算法也是依靠隨機函數選擇插入到上層的數據，進一步加大了算法的隨機性和性能波動。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于區域分級航線圖算法的數據檢索方法，適用于高維大數據的快速近似檢索，實現了快速、精確匹配高維數據，提高了數據檢索效率。

本發明的目的是通過以下方案實現的：

一種基于區域分級航線圖算法的數據檢索方法，包括步驟：通過迭代聚類算法對整個區間的數據進行區域劃分，并主動選擇區域分級航線圖算法中每級的區域大小和分級數來初始化區域分級航線圖，并用于構建索引；利用構建的索引來檢索查詢數據的近似最近鄰。

進一步地，構建索引包括步驟：

S1，載入向量數據；

S2，計算區域分級航線圖算法的分級數和每級的區域大小；

S3，計算區域分級航線圖算法中每級的區域中的數據分布；

S4，將數據集插入到區域分級航線圖算法中；

S5，保存索引文件。

進一步地，利用構建的索引檢索查詢數據的近似最近鄰包括步驟：

S6，加載區域分級航線圖算法的索引文件，獲得區域分級航線圖算法的索引結構；

S7，在區域分級航線圖算法中，利用獲得的索引結構檢索查詢數據的近似最近鄰。