[發明專利]一種基于α叉索引樹的多關鍵詞密文排序檢索方法

有效

• 申請號: 201910014134.1
• 申請日: 2019-01-08
• 公開（公告）號: CN109885640B
• 公開（公告）日: 2021-05-11
• 發明（設計）人: 戴華;李嘯;趙志翔;保靜靜;楊庚;黃海平
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F16/31
• 分類號: G06F16/31;G06F16/33;G06F21/60;G06F21/62
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 康燕文

1.一種基于α叉索引樹的多關鍵詞密文排序檢索方法，其特征在于，包括以下步驟：

(1)數據擁有者生成密鑰K＝{key,S,M₁,M₂}，其中key為加密密鑰，S為隨機向量，M₁和M₂為隨機可逆矩陣；對明文文檔集合進行預處理，通過向量空間模型對明文文檔進行向量化；

(2)通過二分k-means聚類方法對明文文檔集進行二分聚類處理，構建二分聚類樹，最后遍歷該二分聚類樹葉子節點獲取聚類文檔序列；

(3)基于聚類文檔序列，自底向上構建明文α叉索引樹；

(4)通過密鑰key對明文文檔進行加密，通過S、M₁和M₂對α叉索引樹進行加密，將加密后的文檔以及加密索引樹發送至云服務器，同時與授權用戶共享密鑰；

(5)授權用戶根據檢索需求生成檢索向量，通過S、M₁和M₂對檢索向量進行加密處理，生成檢索陷門；

(6)授權用戶將檢索陷門和檢索需返回的文檔數量k發送至云服務器，然后等待接收檢索結果；

(7)云服務器接收到檢索陷門后，采用貪婪深度優先遍歷搜索算法對步驟(4)中索引樹進行檢索，獲取加密文檔向量與檢索陷門內積計算結果最大的k個加密文檔，并作為檢索結果返回給授權用戶；

(8)授權用戶接收到云服務器返回的加密文檔后，通過密鑰key對加密文檔進行解密，進而獲得明文檢索結果；

所述步驟(2)包括以下步驟：

(21)將明文文檔集合DS看成一個原始簇，并作為二分聚類樹的根節點，利用二分k-means聚類方法進行自頂向下的二分處理；

(22)每執行一次二分k-means聚類，原始簇劃分成兩個子簇，將這兩個子簇作為原始簇的兩個孩子節點構建二分聚類樹；不斷遞歸，直到劃分生成的子簇只包含一個文檔為止；

(23)遍歷二分聚類樹中的葉子節點，獲取聚類文檔序列

所述步驟(3)包括以下步驟：

(31)數據擁有者基于步驟(23)中生成的聚類文檔序列中的文檔及向量生成α叉索引樹的葉子節點，并將所有葉子節點加入子層節點序列；

(32)從子層節點序列中依次取α個節點構造父節點，并將父節點加入到父層節點序列中；若子層節點序列中剩余節點數不足α，則將剩余節點直接移入父層節點序列；

(33)將父層節點序列中的節點依次移入子層節點序列，重復步驟(32)，不斷向上構建索引樹，當父層節點序列只含有一個節點時，α叉索引樹構造完成，該節點即為α叉索引樹的根節點；所述α叉索引樹的根節點u的數據結構可以表示為u＝FV,PL,DC，其中α表示中間節點u最多可以包含的孩子節點數量，u.FV是過濾向量，每一維取u所有孩子節點中過濾向量對應位的最大值；u.PL表示孩子節點指針列表，u.DC存儲節點中所有文檔信息；

所述步驟(6)包括以下步驟：

(61)云服務器收到授權用戶上傳的檢索陷門后，采用貪婪深度優先遍歷搜索算法對步驟(4)中索引樹進行檢索；

(62)若檢索節點為中間節點，計算過濾向量和檢索陷門的內積值，如果計算結果大于第k個最相關文檔與檢索陷門的內積值，則繼續向下搜索，否則直接剪枝以該中間節點為根的子樹；

(63)如果檢索節點為葉子節點，計算葉子節點文檔向量與檢索陷門的內積值，獲取與檢索陷門內積值最大的k個文檔作為返回結果。

2.根據權利要求1所述的一種基于α叉索引樹的多關鍵詞密文排序檢索方法，其特征在于，所述步驟(4)包括以下步驟：

(41)利用密鑰key對文檔集合DS中的每個文檔d_i進行加密處理生成密文生成的所有密文構成密文集合

(42)為明文文檔集合DS中的任意文檔d_i生成其對應的明文文檔向量D_i，如果關鍵詞w_j∈d_i則D_i[j]存儲w_j對應的TF值，否則D_i[j]為0；

(43)利用密鑰S對文檔向量D_i根據如下公式拆分成D′_i和D″_i,再利用可逆矩陣M₁,M₂進行加密得到索引向量

3.根據權利要求1所述的一種基于α叉索引樹的多關鍵詞密文排序檢索方法，其特征在于，所述步驟(5)包括以下步驟：

(51)根據檢索關鍵詞集W_q構建檢索向量Q，如果w_i∈W_q，Q[i]中存儲w_i的IDF值，否則Q[i]的值為0；

(52)利用密鑰S，根據如下公式將Q拆分成兩個向量Q′和Q″，

(53)利用M₁和M₂進行加密得到檢索陷門