[發明專利]一種索引生成方法、數據檢索方法和裝置

有效

• 申請號: 201611170581.9
• 申請日: 2016-12-16
• 公開（公告）號: CN106777130B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 崔江濤;馮小康;劉暢;侯勇超;蔡洋
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F16/41
• 分類號: G06F16/41;G06F16/43;G06F16/31;G06F16/33
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 李世喆

1.一種索引生成方法，其特征在于，包括：

提取每一個樣本數據元的樣本特征信息，所述樣本特征信息，包括：樣本特征向量和樣本標識；

為每一個所述樣本特征向量生成對應的近鄰圖索引；

隨機生成至少一個映射向量；

針對每一個所述映射向量，執行：

根據預設的區間寬度，將所述映射向量劃分為至少兩個區間，并為每一個所述區間分配對應的區間標識；

將每一個所述樣本特征向量映射到所述映射向量；

根據映射的結果，將每一個所述樣本標識分配給相關的所述區間標識，生成倒排文檔索引。

2.根據權利要求1所述的方法，其特征在于，

所述為每一個所述區間分配對應的區間標識，包括：

從所述映射向量的起始位置，為每一個所述區間進行順序編號；

確定每一個所述區間的編號為對應的所述區間標識；

和/或，

所述為每一個所述樣本特征向量生成對應的近鄰圖索引，包括：

針對每一個所述樣本特征向量，執行：

為所述樣本特征向量查找至少一個近鄰樣本特征向量；

從所述樣本特征向量開始，向每一個所述近鄰樣本特征向量繪制對應的有向邊，形成所述樣本特征向量的近鄰圖索引；

和/或，

進一步包括：構建數據空間；

所述將每一個所述樣本特征向量映射到所述映射向量，根據映射的結果，將每一個所述樣本標識分配給相關的所述區間標識，包括：

將每一個所述樣本數據元對應的樣本特征向量和至少一個映射向量加載到所述數據空間；

將每一個所述樣本特征向量抽象為所述數據空間中的一個數據點，并將每一個所述映射向量抽象為所述數據空間中的一條有向線段；

針對每一個所述樣本特征向量對應的數據點，執行：

將所述樣本特征向量對應的數據點投影到每一個所述映射向量對應的有向線段上，并確定所述數據點在每一個所述映射向量對應的有向線段的投影位置；

將所述樣本特征向量對應的所述樣本標識分配給所述投影位置所屬區間。

3.根據權利要求1所述的方法，其特征在于，所述將每一個所述樣本特征向量映射到所述映射向量，根據映射的結果，將每一個所述樣本標識分配給相關的所述區間標識，包括：

基于所述映射向量，計算每一個所述樣本特征向量的哈希值；

針對每一個所述樣本標識，執行：

當所述樣本標識對應的所述樣本特征向量的哈希值與當前區間標識一致時，將所述樣本標識分配給所述當前區間標識。

4.根據權利要求3所述的方法，其特征在于，所述基于所述映射向量，計算每一個所述樣本特征向量的哈希值，包括：

根據下述第一計算公式，計算每一個所述樣本特征向量的哈希值；

第一計算公式：

其中，h(x)表征哈希值；a表征所述映射向量；x表征樣本特征向量；w表征所述預設的區間寬度；b表征預設的偏移量且b∈[0，w)。

5.一種數據檢索方法，其特征在于，利用權利要求1至4任一所述的方法為至少兩個樣本數據元生成至少一個近鄰圖索引和至少一個倒排文檔索引，還包括：

當接收到檢索信息時，提取所述檢索信息包含的檢索特征向量；

針對每一個所述倒排文檔索引，執行：

基于所述倒排文檔索引，計算所述檢索特征向量對應的哈希值；

利用所述檢索特征向量對應的哈希值、所述倒排文檔索引以及所述至少一個近鄰圖索引進行檢索。

6.根據權利要求5所述的方法，其特征在于，所述基于所述倒排文檔索引，計算所述檢索特征向量對應的哈希值，包括：

根據下述第二計算公式，計算所述檢索特征向量對應的哈希值；

第二計算公式：

其中，f(y)表征所述檢索特征向量對應的哈希值；β_i表征倒排文檔索引i對應的映射向量；y表征所述檢索特征向量；w表征所述倒排文檔索引對應的區間寬度；δ表征為所述檢索特征向量預設的偏移量。