[發明專利]一種面向多模式圖匹配的并行加速方法

有效

• 申請號: 201811228936.4
• 申請日: 2018-10-22
• 公開（公告）號: CN109614520B
• 公開（公告）日: 2021-06-04
• 發明（設計）人: 于靜;郭晶晶;劉小梅;劉燕兵;曹聰;譚建龍;郭莉
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 司立彬

1.一種面向多模式圖匹配的并行加速方法，其步驟包括：

1)生成目標領域的模式圖集的多模式圖索引；

2)對所述多模式圖索引采用逐層分組策略，即對所述多模式圖索引中每一層出現的模式圖進行評估，得到該層中每個模式圖的匹配代價，然后根據匹配代價對該層的模式圖進行分組；其中得到每個模式圖的匹配代價的方法為：首先根據模式圖是否存在同構子圖將模式圖分為基礎模式圖和擴展模式圖；所述基礎模式圖是指在模式圖集P＝{P₁，P₂，...，P_n}中，如果P_i∈P并且P_i的任意子圖不屬于P，那么P_i稱為基礎模式圖，P為模式圖P_i所在層的模式圖集合；所述擴展模式圖是指在模式圖集P＝{P₁，P₂，...，P_n}中，如果P_i∈P并且存在P_i的某一子圖屬于P，那么P_i稱為擴展模式圖；然后對于基礎模式圖，其匹配代價為Cost(p_i)＝|N_i|*(|V_i|+|E_i|)，其中，N_i表示模式圖P_i待匹配的數據規模，V_i和E_i分別表示模式圖P_i中結點和邊的集合；對于擴展模式圖，其匹配代價為Cost(p_j)＝|I_F(j)|*Score(j，F(j))，其中，F(j)代表模式圖p_j的父模式圖，I_F(j)表示F(j)在模式圖p_j所在層的上一層的匹配結果，Score(j，F(j))表示模式圖p_j與模式圖F(j)在所述多模式圖索引中所對應邊的權重；

3)對不同分組分別分配一線程同時進行匹配計算。

2.如權利要求1所述的方法，其特征在于，生成所述多模式圖索引的方法為：首先生成所述模式圖集的模式關聯圖；所述模式關聯圖是一個由模式圖為結點、模式圖間同構關系為邊的有向無環圖，記錄模式圖集中所有的子圖同構關系；然后基于所述模式關聯圖構建的確定根結點情況下的最小生成樹作為所述多模式圖索引。

3.如權利要求2所述的方法，其特征在于，對于所述模式關聯圖中，如果一個節點具有多個父節點，則保留該節點與其多個父節點的所有有向邊中權重最小的邊，其余的邊刪除，形成所述最小生成樹。

4.如權利要求3所述的方法，其特征在于，模式圖P_i與P_j之間的有向邊E_ij的權重為Score(j，i)＝|V_j|-|V_i|+|E_j|-|E_i|；其中，|V_i|代表模式圖P_i的結點數，|E_i|代表模式圖P_i的邊數，|V_j|代表模式圖P_j的結點數，|E_j|代表模式圖P_j的邊數。

5.如權利要求1所述的方法，其特征在于，根據匹配代價對同一層的模式圖進行分組的方法為：基于模式圖的匹配代價，采用分割問題中的完全貪心算法實現模式圖的分組：首先根據模式圖的匹配代價計算模式圖的權重，將同一層中的模式圖分為權重之和相差最小的若干組。

6.如權利要求5所述的方法，其特征在于，根據模式圖的權重對模式圖進行降序排列，選擇前k個模式圖作為初始分組結果，對剩余的每個模式圖選擇當前權重之和最小的組加入，直到所有模式圖被劃分到各個組。