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

有效

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

本說明書實施例提供一種利用向量圖索引從數據庫中檢索節點向量的方法及裝置。向量圖索引將數據庫中的各個節點劃分在從高到低的各個層中，高層中節點的數量小于低層中節點的數量，每一層的節點在該層以及該層以下的各層中均存在設定數目的鄰居，且高層的鄰居數目小于低層的鄰居數目，節點的向量與其鄰居節點的向量之間的匹配度大于預設閾值。在檢索時，基于向量圖索引，按照從最高層到最低層的順序依次，從每層的入口節點、入口節點在本層的鄰居節點，以及鄰居節點在本層的鄰居節點中，確定與待檢索節點在向量上匹配目標節點，基于本層的目標節點確定下一層的入口節點，并基于從最低層中確定出的目標節點，確定針對第一節點檢索得到的節點。

技術領域

本說明書一個或多個實施例涉及數據檢索領域，尤其涉及的一種利用向量圖索引從數據庫中檢索節點向量的方法及裝置。

背景技術

隨著計算機技術的發展，數據包含的信息也越來越多，對數據的檢索要求也逐漸升高。通?？梢圆捎酶呔S向量來表示包含較多信息的數據，例如，圖像、用戶特征等數據均可以采用高維向量進行表示。在一些應用場景中，存在對高維向量進行檢索的要求。例如，在刷臉支付時，可以從數據庫的大量人臉圖像中對輸入的人臉圖像進行檢索；在購物網站上，可以從數據庫的大量商品圖像中對輸入的商品圖像進行檢索。PostgreSQL是一款支持向量檢索的開源數據庫，其具有高可用性、高擴展性。隨著數據數目的增多以及向量維數的升高，基于該數據庫的向量檢索效率，成為目前技術改進的一個重點方向。

因此，希望能有改進的方案，可以提高基于PostgreSQL數據庫進行高維向量檢索時的檢索效率。

發明內容

本說明書一個或多個實施例描述了利用向量圖索引從數據庫中檢索節點向量的方法及裝置，以提高基于PostgreSQL數據庫進行高維向量檢索時的檢索效率。具體的計算方案如下。

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

獲取待檢索的第一節點；

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

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

在一種實施方式中，所述向量圖索引包括多個數據頁和多個鄰居頁，所述數據頁用于存儲各個節點的向量，所述鄰居頁用于存儲各個節點在各層中的鄰居節點以及該鄰居節點的起始鄰居頁，一個節點的所有鄰居節點處于一個鄰居頁中或者連續的多個鄰居頁中，不同節點的鄰居節點位于不同的鄰居頁中。

在一種實施方式中，所述從所述入口節點、所述入口節點在所述當前層的鄰居節點以及該鄰居節點在所述當前層的鄰居節點中，確定與所述第一節點在向量上最匹配的目標節點的步驟，包括：

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

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

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