[發明專利]一種結合VP樹和導向近鄰圖的近似最近鄰搜索方法

在審

• 申請號: 202011223218.5
• 申請日: 2020-11-05
• 公開（公告）號: CN112287185A
• 公開（公告）日: 2021-01-29
• 發明（設計）人: 徐小良;馬丁程;王宇翔
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 浙江千克知識產權代理有限公司 33246
• 代理人: 周希良

本發明提出的一種結合VP樹和導向近鄰圖的近似最近鄰搜索方法，該方法包括兩個過程：索引構建過程和搜索過程。索引構建過程包含：(1)針對高維向量數據構建存放入口點的VP樹；(2)使用可導航伸展圖將高維向量數據構建成K近鄰圖；(3)將K近鄰圖中的每個點的鄰居集均勻地劃分來得到可導向近鄰圖。搜索過程包含：(1)查找入口點階段，通過搜索VP樹快速得到大致接近查詢點的入口點；(2)導向搜索階段，從入口點開始，得到查詢點的局部最近點；(3)窮盡搜索階段，利用范圍搜索算法窮盡搜索查詢點附近的點并返回查詢點的top–K個最近點。本發明使用混合式搜索策略有效提升了近似最近鄰搜索的性能。

技術領域

本發明涉及近似最近鄰搜索領域，具體涉及一種結合VP樹和導向近鄰圖的近似最近鄰搜索方法。

背景技術

近似最近鄰搜索是數據挖掘、機器學習、機器視覺和信息檢索等鄰域的一個關鍵技術，在過去的幾十年中，人們一直致力于提高近似最近鄰搜索的性能。目前近似最近鄰搜索包括以下四類方法：基于樹、基于哈希、基于量化和基于近鄰圖的方法，相比于其他的方法，基于近鄰圖的方法因其精度更高且速度更快的特點，成為近幾年的研究熱點。

目前已經有分層可導航小世界圖(HNSW)、可導航衛星系圖(NSSG)、可導航伸展圖(NSG)等優秀的方法被提出，他們在實際生產環境中得到了廣泛的應用，但是包括上述的大部分基于近鄰圖的近似最近鄰搜索方法都存在一個問題：基于近鄰圖的方法的圖搜索策略都僅僅使用單一的貪婪搜索算法，這會導致搜索的低效率問題，由于貪婪搜索算法在搜索過程中需要遍歷當前訪問點的所有鄰居點并與查詢點進行相似度計算，這在遠離查詢點的搜索區域是完全沒有必要的，并且會嚴重降低搜索效率，尤其是針對大規模高維數據的情況下，搜索效率的優化更是面臨的一個主要挑戰。

發明內容

本發明針對現有技術的不足，提出了一種結合VP樹和導向近鄰圖的近似最近鄰搜索方法，這種方法包括兩個過程：索引構建過程和搜索過程。

索引構建過程包含三個步驟：(1)針對高維向量數據構建用于搜索入口點的VP樹；(2)使用可導航伸展圖(NSG)將高維向量數據構建成K近鄰圖；(3)基于VP樹將K近鄰圖中的每個點的鄰居集均勻地劃分為子鄰居集left和子鄰居集right得到可導向近鄰圖。

搜索過程包含三個階段：查找入口點階段、導向搜索階段和窮盡搜索階段。在查找入口點階段，通過搜索VP樹，快速得到大致接近查詢點的入口點。在導向搜索階段，從入口點開始，利用基于VP樹的導向搜索算法高效的收斂并得到查詢點的局部最近點。在窮盡搜索階段，從查詢點的局部最近點開始，利用范圍搜索算法窮盡的搜索查詢點附近的點，最后將返回的點作為搜索結果。

這種結合VP樹和導向近鄰圖的近似最近鄰搜索方法避免了在遠離查詢點的搜索區域窮盡的遍歷所有的鄰居點帶來的低效問題，從而達到了快速收斂的目的，并且通過對查詢點附近的搜索區域進行窮盡的搜索來保證最終結果的精度。

本發明所提出的一種結合VP樹和導向近鄰圖的近似最近鄰搜索方法包含索引構建過程和搜索過程，具體內容如下：

(1)索引構建過程：首先構建存放入口點的VP樹，然后將高維向量數據構建成K近鄰圖，最后基于VP樹和K近鄰圖生成可導向K近鄰圖；

(1-1)針對高維向量數據構建存放入口點的VP樹；

(1-2)使用可導航伸展圖(NSG)將高維向量數據構建成K近鄰圖；

(1-3)基于VP樹將K近鄰圖中的每個點的鄰居集均勻地劃分為子鄰居集left和子鄰居集right得到可導向近鄰圖。

(2)執行搜索過程，搜索過程包括三個階段：查找入口點階段、導向搜索階段和窮盡搜索階段；

(2-1)查找入口點階段：通過搜索存放入口點的VP樹，快速得到大致接近查詢點的入口點；