[發明專利]一種應用于頻繁子圖查詢的頻繁子圖索引方法及裝置

在審

• 申請號: 202111055107.2
• 申請日: 2021-09-09
• 公開（公告）號: CN113722551A
• 公開（公告）日: 2021-11-30
• 發明（設計）人: 畢立偉;孫喜民;周晶;李曉明;王帥;孫博
• 申請（專利權）人: 國網電子商務有限公司;國網電商科技有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 尹秀

1.一種應用于頻繁子圖查詢的頻繁子圖索引方法，其特征在于，包括：

確定頻繁子圖集，將所述頻繁子圖集劃分為各個圖集塊，為所述各個圖集塊建立外存索引；

為所述頻繁子圖中的各個頻繁子圖建立內存索引，將各個內存索引存入內存中，將所述外存索引和所述各個圖集塊存入外存中；

在接收對目標圖的查詢請求的情況下，判斷所述目標圖是否為頻繁子圖；

若是，在所述內存中確定所述目標圖的目標內存索引，基于所述目標內存索引在所述外存中確定所述目標圖所屬目標圖集塊，獲取所述目標圖集塊的目標外存索引；

基于所述目標內存索引和所述目標外存索引為所述目標圖建立目標連接。

2.根據權利要求1所述的方法，其特征在于，為所述頻繁子圖中的各個頻繁子圖建立內存索引，包括：

獲取每個頻繁子圖的屬性特征；

為每個頻繁子圖分配內存索引，將所述內存索引與對應的屬性特征建立關聯。

3.根據權利要求1所述的方法，其特征在于，判斷所述目標圖是否為頻繁子圖，包括：

獲取所述目標圖中的各個點和各個邊；

將所述各個點與預設基準頻繁子圖中的各個基準點進行比較，和，將所述各個邊與所述預設基準頻繁子圖中的各個基準邊進行比較；

判斷所述各個點和所述各個邊的比較結果是否滿足預設的相似度閾值。

4.根據權利要求1所述的方法，其特征在于，基于所述目標內存索引和所述目標外存索引為所述目標圖建立目標連接，包括：

基于所述目標內存索引確定第一最短路徑；

基于所述目標外存索引確定第二最短路徑；

基于所述第一最短路徑和所述第二最短路徑確定所述目標鏈接。

5.根據權利要求4所述的方法，其特征在于，還包括：

若否，為所述目標圖在所述內存中建立內存索引，

檢索所述內存索引在所述內存中的第三最短路徑；

基于所述第二最短路徑與所述第三最短路徑確定所述目標連接。

6.一種應用于頻繁子圖查詢的頻繁子圖索引裝置，其特征在于，包括：

劃分和建立模塊，用于確定頻繁子圖集，將所述頻繁子圖集劃分為各個圖集塊，為所述各個圖集塊建立外存索引；

第一建立模塊，用于為所述頻繁子圖中的各個頻繁子圖建立內存索引，將各個內存索引存入內存中，將所述外存索引和所述各個圖集塊存入外存中；

判斷模塊，用于在接收對目標圖的查詢請求的情況下，判斷所述目標圖是否為頻繁子圖；

確定和獲取模塊，用于若是，在所述內存中確定所述目標圖的目標內存索引，基于所述目標內存索引在所述外存中確定所述目標圖所屬目標圖集塊，獲取所述目標圖集塊的目標外存索引；

第二建立模塊，用于基于所述目標內存索引和所述目標外存索引為所述目標圖建立目標連接。

7.根據權利要求6所述的裝置，其特征在于，所述第一建立模塊包括：

第一獲取單元，用于獲取每個頻繁子圖的屬性特征；

分配和建立單元，用于為每個頻繁子圖分配內存索引，將所述內存索引與對應的屬性特征建立關聯。

8.根據權利要求6所述的裝置，其特征在于，所述判斷模塊包括：

第二獲取單元，用于獲取所述目標圖中的各個點和各個邊；

比較單元，用于將所述各個點與預設基準頻繁子圖中的各個基準點進行比較，和，將所述各個邊與所述預設基準頻繁子圖中的各個基準邊進行比較；

判斷單元，用于判斷所述各個點和所述各個邊的比較結果是否滿足預設的相似度閾值。

9.根據權利要求6所述的裝置，其特征在于，所述第二建立模塊包括：

第一確定單元，用于基于所述目標內存索引確定第一最短路徑；

第二確定單元，用于基于所述目標外存索引確定第二最短路徑；

第三確定單元，用于基于所述第一最短路徑和所述第二最短路徑確定所述目標鏈接。

10.根據權利要求9所述的裝置，其特征在于，還包括：

建立單元，用于若否，為所述目標圖在所述內存中建立內存索引，

檢索單元，用于檢索所述內存索引在所述內存中的第三最短路徑；

第四確定單元，用于基于所述第二最短路徑與所述第三最短路徑確定所述目標連接。