[發明專利]利用向量圖索引從數據庫中檢索節點向量的方法及裝置

有效

• 申請號: 202010136299.9
• 申請日: 2020-03-02
• 公開（公告）號: CN111400314B
• 公開（公告）日: 2023-10-27
• 發明（設計）人: 李濤;楊文;魏宏;方概
• 申請（專利權）人: 支付寶（杭州）信息技術有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/24
• 代理公司: 北京億騰知識產權代理事務所(普通合伙) 11309
• 代理人: 陳霽;周良玉

1.一種利用向量圖索引從PostgreSQL數據庫中檢索節點向量的方法，通過計算機執行；所述數據庫包含多個節點的向量；所述向量圖索引將所述數據庫中的各個節點劃分在從高到低的各個層中，高層中節點的數量小于低層中節點的數量，每一層中的節點在該層以及該層以下的各層中均存在設定數目的鄰居，且高層的鄰居數目小于低層的鄰居數目；所述方法包括：

獲取待檢索的第一節點；

基于所述向量圖索引，按照從最高層到最低層的順序依次將每個層確定為當前層，并針對確定的每一個當前層，按照以下方式確定所述當前層的目標節點：確定所述當前層的入口節點，從所述入口節點、所述入口節點在所述當前層的鄰居節點以及該鄰居節點在所述當前層的鄰居節點中，確定與所述第一節點在向量上最匹配的目標節點；其中，當所述當前層是最高層時，從所述最高層中任意選擇節點作為所述最高層的入口節點；當所述當前層不是最高層時，基于所述當前層的上一層確定的目標節點，確定所述當前層的入口節點；

基于從最低層中確定出的目標節點，確定針對所述第一節點檢索得到的節點。

2.根據權利要求1所述的方法，所述向量圖索引包括多個數據頁和多個鄰居頁，所述數據頁用于存儲各個節點的向量，所述鄰居頁用于存儲各個節點在各層中的鄰居節點以及該鄰居節點的起始鄰居頁，一個節點的所有鄰居節點處于一個鄰居頁中或者連續的多個鄰居頁中，不同節點的鄰居節點位于不同的鄰居頁中。

3.根據權利要求2所述的方法，所述從所述入口節點、所述入口節點在所述當前層的鄰居節點以及該鄰居節點在所述當前層的鄰居節點中，確定與所述第一節點在向量上最匹配的目標節點的步驟，包括：

將所述入口節點確定為當前節點；

基于所述向量圖索引，獲取所述當前節點的鄰居頁，從所述當前節點的鄰居頁中獲取所述當前節點在所述當前層的各個第一鄰居節點；

從所述數據頁中獲取各個第一鄰居節點的向量以及所述當前節點的向量，并與所述第一節點的向量進行匹配，得到一個最匹配鄰居節點；

將所述最匹配鄰居節點作為當前節點，返回執行所述基于所述向量圖索引，獲取所述當前節點的鄰居頁的步驟，當循環滿足收斂條件時，將本次的最匹配鄰居節點作為所述目標節點。

4.根據權利要求3所述的方法，所述基于所述當前層的上一層確定的目標節點，確定所述當前層的入口節點的步驟，包括：

將所述當前層的上一層確定的一個目標節點，確定為所述當前層的入口節點。

5.根據權利要求2所述的方法，所述從所述入口節點、所述入口節點在所述當前層的鄰居節點以及該鄰居節點在所述當前層的鄰居節點中，確定與所述第一節點在向量上最匹配的目標節點的步驟，包括：

將所述入口節點確定為當前節點；

基于所述向量圖索引，獲取所述當前節點的鄰居頁，從所述當前節點的鄰居頁中獲取所述當前節點在所述當前層的各個第一鄰居節點；

從所述數據頁中獲取各個第一鄰居節點的向量以及所述當前節點的向量，并與所述第一節點的向量進行匹配，按照向量的匹配度大小將所述各個第一鄰居節點和所述當前節點加入匹配隊列中；

按照匹配度從大到小的順序，將所述匹配隊列中的節點依次作為當前節點，返回執行所述基于所述向量圖索引，獲取所述當前節點的鄰居頁的步驟，當所述匹配隊列滿足收斂條件時，將所述匹配隊列中匹配度最大的第一數量個節點作為所述目標節點。

6.根據權利要求5所述的方法，所述基于從最低層中確定出的目標節點，確定針對所述第一節點檢索得到的節點的步驟，包括：

基于從最低層中確定出的第一數量個目標節點，確定針對所述第一節點檢索得到的節點。