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

在審

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

本發明公開了一種應用于頻繁子圖查詢的頻繁子圖索引方法及裝置，確定頻繁子圖集，將頻繁子圖集劃范圍各個圖集塊，為各個圖集塊建立外存索引；為頻繁子圖中的各個頻繁子圖建立內存索引，將各個內存索引存入內存中，將各個內存索引、外存索引和各個圖集塊存入外存中；在接收對目標圖的查詢請求的情況下，判斷目標圖是否為頻繁子圖；若是，在內存中確定所述目標圖的目標內存索引，基于目標內存索引在外存中確定目標圖所屬目標圖集塊，獲取目標圖集塊的目標外存索引；基于目標內存索引和目標外存索引為所述目標圖建立目標連接。在對目標圖進行查詢過程中，基于內存索引和外存索引實現了對目標圖的查詢，不需要提取目標圖的特征，提高了查詢的速度。

技術領域

本發明涉及數據挖掘技術領域，尤其涉及一種應用于頻繁子圖查詢的頻繁子圖索引方法及裝置。

背景技術

頻繁子圖：從動態演繹圖序列中找到一組子圖序列，使得其滿足：(1)這些子圖在動態圖序列中的出現是頻繁的；(2)這些子圖的圖序列隨時間變化的情況保持一致。

目前，隨著互聯網的蓬勃發展，網絡的規模在不斷的擴大，在大型圖數據處理過程中，傳統的圖模式挖掘算法隨著支持度的減小，在時間或空間上代價逐漸增長，在一些特征提取方面也較為復雜，使得挖掘任務很難在合理的時間完成。

發明內容

有鑒于此，本發明提供了一種應用于頻繁子圖查詢的頻繁子圖索引方法及裝置，用于解決傳統的圖模式挖掘算法隨著支持度的減小，在時間或空間上代價逐漸增長，在一些特征提取方面也較為復雜，使得挖掘任務很難在合理的時間完成的問題，具體方案如下：

一種應用于頻繁子圖查詢的頻繁子圖索引方法，包括：

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

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

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

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

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

上述的方法，可選的，為所述頻繁子圖中的各個頻繁子圖建立內存索引，包括：

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

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

上述的方法，可選的，判斷所述目標圖是否為頻繁子圖，包括：

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

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

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

上述的方法，可選的，基于所述目標內存索引和所述目標外存索引為所述目標圖建立目標連接，包括：

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

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

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

上述的方法，可選的，還包括：

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

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