[發明專利]一種基于學習索引的KNN查詢方法

有效

• 申請號: 202211701214.2
• 申請日: 2022-12-28
• 公開（公告）號: CN115858629B
• 公開（公告）日: 2023-06-23
• 發明（設計）人: 黎玲利;韓奧
• 申請（專利權）人: 黑龍江大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/22;G06N3/08;G06F18/214;G06F18/2413;G06N3/0464
• 代理公司: 哈爾濱市松花江聯合專利商標代理有限公司 23213
• 代理人: 岳昕

1.一種基于學習索引的KNN查詢方法，其特征在于：它包括以下步驟：

S1、獲取一定數量的計算機數據作為數據集，按照Zipfian分布將計算機數據劃分為訓練集和測試集；

S2、利用傳統索引將數據集的數據空間劃分為y個不重疊的分區，并得到訓練集中每個訓練數據的KNN所在的分區，如果當前分區有KNN結果，則當前分區標簽對應位置置為1，否則置為0，得到所有訓練數據及其對應的分區；

S3、建立深度學習模型，利用所有訓練數據及其對應的分區對深度學習模型進行訓練，輸入訓練數據，輸出訓練數據在對應分區的概率，得到訓練好的深度學習模型；

S4、選取訓練數據對應的概率最大的T個分區，并獲得與訓練數據真實K近鄰的k個點，在訓練數據和每個分區之間建立一條帶權重的邊，在每個點與每個分區之間建立一條帶權重的邊；

將訓練數據與對應的k個點作為一個集合，得到集合中每個點到各個分區的邊的權重，以及每個點的總權重，根據每個點的總權重從大到小對集合中的點進行排序，得到排序后的點，根據排序后的點，將與每個點相連的各個邊按照邊的權重從大到小進行排序，根據邊的排序結果將點分配到權重最大的分區內，如果權重最大的分區內數據容量達到給定閾值，則將點分配到權重次大的分區內，直到所有點分配到分區內，得到精化后的分區；

S5、將測試集中的某條測試數據輸入深度學習模型，得到某條測試數據對應的概率，選取概率中數值最大的前T個數值，得到每個數值對應的索引號I，將精化后的分區中索引號為I的分區作為候選分區，將候選分區中的所有數據點作為某條測試數據的KNN候選點集，從候選點集中找到距離某條測試數據最近的K個點，即為某條測試數據的KNN結果。

2.根據權利要求1中所述的一種基于學習索引的KNN查詢方法，其特征在于：S3中建立深度學習模型，利用所有訓練數據及其對應的分區對深度學習模型進行訓練，輸入訓練數據，輸出訓練數據在對應分區的概率，得到訓練好的深度學習模型，具體過程為：

深度學習模型依次包括三個模塊，模塊一采用深度可分離卷積，輸入訓練數據q，輸出特征向量h1；模塊二依次包括兩個卷積塊，輸入訓練數據q和特征向量h1，輸出特征向量h2；將特征向量h1和特征向量h2相乘，得到向量h3,模塊三依次包括一個卷積層、一個池化層和一個1*1卷積層，輸入h3，輸出訓練數據q在對應的不同分區的概率向量h。

3.根據權利要求1中所述的一種基于學習索引的KNN查詢方法，其特征在于：模塊二中每個卷積塊依次包括三個卷積層、一個池化層、兩個卷積層、一個池化層、一個全連接層。

4.一種基于學習索引的KNN查詢系統，包括存儲器、處理器以及存儲在所述存儲器中并可在所述處理器上運行的計算機程序，其特征在于：所述處理器執行所述計算機程序時實現如權利要求1-3任一所述方法的步驟。

5.一種計算機可讀存儲介質，所述計算機可讀存儲介質存儲有計算機程序，其特征在于：所述計算機程序被處理器執行時實現如權利要求1-3任一所述方法的步驟。