買專利賣專利找龍圖騰，真高效！ 查專利查商標(biāo)用IPTOP,全免費！專利年費監(jiān)控用IP管家,真方便！

龍圖騰網(wǎng)獲悉東北大學(xué)申請的專利一種面向動態(tài)圖的異構(gòu)協(xié)同子圖匹配方法獲國家發(fā)明授權(quán)專利權(quán)，本發(fā)明授權(quán)專利權(quán)由國家知識產(chǎn)權(quán)局授予，授權(quán)公告號為：CN120067713B 。

龍圖騰網(wǎng)通過國家知識產(chǎn)權(quán)局官網(wǎng)在2025-08-26發(fā)布的發(fā)明授權(quán)授權(quán)公告中獲悉：該發(fā)明授權(quán)的專利申請?zhí)?專利號為：202510535174.6，技術(shù)領(lǐng)域涉及：G06F18/22；該發(fā)明授權(quán)一種面向動態(tài)圖的異構(gòu)協(xié)同子圖匹配方法是由李傳文;李季;武文軒;張一杰設(shè)計研發(fā)完成，并于2025-04-27向國家知識產(chǎn)權(quán)局提交的專利申請。

本一種面向動態(tài)圖的異構(gòu)協(xié)同子圖匹配方法在說明書摘要公布了：本申請?zhí)岢鲆环N面向動態(tài)圖的異構(gòu)協(xié)同子圖匹配方法，子圖匹配技術(shù)領(lǐng)域，方法包括：獲取數(shù)據(jù)圖、查詢圖集合以及動態(tài)更新序列；將數(shù)據(jù)圖保存到GPU中；將數(shù)據(jù)圖與動態(tài)更新序列保存到CPU中，采用動態(tài)更新序列更新數(shù)據(jù)圖；根據(jù)查詢圖集合，使用GPU中的數(shù)據(jù)圖進(jìn)行并行的子圖匹配，得到第一子圖匹配結(jié)果；根據(jù)查詢圖集合以及動態(tài)更新序列，使用CPU中的數(shù)據(jù)圖進(jìn)行子圖匹配，得到第二子圖匹配結(jié)果；將第一子圖匹配結(jié)果與第二子圖匹配結(jié)果進(jìn)行合并，得到最終的子圖匹配結(jié)果，并且根據(jù)動態(tài)更新序列更新GPU中的數(shù)據(jù)圖。本申請的方法大大縮小了子超圖匹配所需的時間。

本發(fā)明授權(quán)一種面向動態(tài)圖的異構(gòu)協(xié)同子圖匹配方法在權(quán)利要求書中公布了：1.一種面向動態(tài)圖的異構(gòu)協(xié)同子圖匹配方法，其特征在于，包括： 獲取數(shù)據(jù)圖、查詢圖集合以及動態(tài)更新序列； 將數(shù)據(jù)圖保存到GPU中； 將數(shù)據(jù)圖與動態(tài)更新序列保存到CPU中，采用動態(tài)更新序列更新數(shù)據(jù)圖； 根據(jù)查詢圖集合，使用GPU中的數(shù)據(jù)圖進(jìn)行并行的子圖匹配，得到第一子圖匹配結(jié)果； 根據(jù)查詢圖集合以及動態(tài)更新序列，使用CPU中的數(shù)據(jù)圖進(jìn)行子圖匹配，得到第二子圖匹配結(jié)果； 將第一子圖匹配結(jié)果與第二子圖匹配結(jié)果進(jìn)行合并，得到最終的子圖匹配結(jié)果，并且根據(jù)動態(tài)更新序列更新GPU中的數(shù)據(jù)圖； 所述根據(jù)查詢圖集合，使用GPU中的數(shù)據(jù)圖進(jìn)行并行的子圖匹配，得到第一子圖匹配結(jié)果，包括： 在靜態(tài)數(shù)據(jù)圖中找到查詢圖集合中每一個元素中每個節(jié)點的候選集； 根據(jù)每個節(jié)點的候選集生成每條邊的候選集； 根據(jù)每個節(jié)點的候選集以及每條邊的候選集，將查詢圖集合中每一個元素轉(zhuǎn)化為一棵邊生成樹； 將一棵邊生成樹拆分為多個獨立查詢邊； 利用GPU并行處理多個獨立查詢邊，在每條獨立查詢邊中找到分支候選結(jié)果； 根據(jù)每個獨立查詢邊的分支交點，對每個分支候選結(jié)果進(jìn)行拼接，得到第一子圖匹配結(jié)果； 所述根據(jù)查詢圖集合以及動態(tài)更新序列，使用CPU中的數(shù)據(jù)圖進(jìn)行子圖匹配，得到第二子圖匹配結(jié)果，包括： 通過查詢圖集合中的查詢圖中頂點的最大跳數(shù)，找到受動態(tài)更新序列更新影響的區(qū)域，將所述區(qū)域作為動態(tài)數(shù)據(jù)子圖； 判斷數(shù)據(jù)圖中每個更新節(jié)點在更新前后是否是查詢圖中某個節(jié)點的候選節(jié)點，如果是，則以修改后的節(jié)點為起點進(jìn)行對應(yīng)查詢圖中頂點的最大跳數(shù)的深度優(yōu)先遍歷，將所有更新節(jié)點的深度優(yōu)先遍歷所組成的子圖作為增量數(shù)據(jù)子圖；如果否，則跳過這個更新節(jié)點，不進(jìn)行任何操作； 根據(jù)第三過濾規(guī)則、第四過濾規(guī)則以及第五過濾規(guī)則，在增量數(shù)據(jù)子圖中找到查詢圖集合中的查詢圖中每個節(jié)點的候選集； 根據(jù)第二計算函數(shù)的函數(shù)值從小到大的順序，確定增量數(shù)據(jù)子圖匹配的查詢順序； 為每個節(jié)點的候選集建立輔助存儲結(jié)構(gòu)，所述輔助存儲結(jié)構(gòu)為通過過濾之后找到每個查詢頂點在數(shù)據(jù)圖中存在匹配關(guān)系的數(shù)據(jù)頂點的集合以及記錄數(shù)據(jù)頂點之間是否存在邊； 根據(jù)輔助存儲結(jié)構(gòu)以及回溯算法，找到動態(tài)數(shù)據(jù)子圖中所有查詢圖同構(gòu)的子圖，得到第二子圖匹配結(jié)； 所述第三過濾規(guī)則，為標(biāo)簽過濾規(guī)則，根據(jù)查詢圖中的查詢節(jié)點的標(biāo)簽信息，在增量數(shù)據(jù)子圖中為查詢節(jié)點生成候選節(jié)點； 所述第四過濾規(guī)則，為度過濾規(guī)則，根據(jù)查詢圖中的查詢節(jié)點的度信息，在增量數(shù)據(jù)子圖中為查詢節(jié)點生成候選節(jié)點； 所述第五過濾規(guī)則，為鄰居標(biāo)簽頻率過濾規(guī)則，利用查詢圖中的查詢節(jié)點的鄰居節(jié)點Nu按照以下方式過濾：給定節(jié)點v∈Cu，如果存在一個標(biāo)簽l∈LNu，則存在|Nv，l|＞|Nu，l|，其中LNu＝{Lu′|u′∈Nu}，Nu,I＝{u′∈Nu|Lu′＝l}，如果不存在一個標(biāo)簽l∈LNu，則將節(jié)點v過濾出去，其中，u為查詢圖中的查詢節(jié)點，Nu為u的鄰居節(jié)點，v為數(shù)據(jù)圖中的節(jié)點，Cu為u的匹配候選集，LNu為u的鄰居節(jié)點的標(biāo)簽，|Nv，l|為v的鄰居節(jié)點中標(biāo)簽是l的節(jié)點的數(shù)量，|Nu，l|為u的鄰居節(jié)點中標(biāo)簽是l的節(jié)點的數(shù)量，u’為查詢圖中的另一個查詢節(jié)點，LNu’為u’的鄰居節(jié)點的標(biāo)簽； 所述第二計算函數(shù)，計算式如下：f’u＝|C’udu|； 其中，f’u為第二計算函數(shù)，C’u為經(jīng)過過濾后的查詢圖中每個節(jié)點的候選集，du為查詢圖集合中某一查詢節(jié)點u的度大小。

如需購買、轉(zhuǎn)讓、實施、許可或投資類似專利技術(shù)，可聯(lián)系本專利的申請人或?qū)＠麢?quán)人東北大學(xué)，其通訊地址為：110819 遼寧省沈陽市和平區(qū)文化路三號巷11號；或者聯(lián)系龍圖騰網(wǎng)官方客服，聯(lián)系龍圖騰網(wǎng)可撥打電話0551-65771310或微信搜索“龍圖騰網(wǎng)”。