[發明專利]一種子圖匹配方法、裝置、設備及存儲介質

在審

• 申請號: 202011623281.8
• 申請日: 2020-12-30
• 公開（公告）號: CN112667860A
• 公開（公告）日: 2021-04-16
• 發明（設計）人: 劉元弘;王釗
• 申請（專利權）人: 海南普適智能科技有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/9035;G06F16/903
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 劉翠香

本申請公開了一種子圖匹配方法，該方法包括以下步驟：根據預設的查詢規則構建查詢圖，查詢圖為一層或多層樹結構，包括多個查詢節點，每個查詢節點具有各自的節點類型，查詢節點之間的邊表示查詢節點間關系；根據查詢圖的各查詢節點類型和查詢節點間關系，對原始圖進行點邊過濾處理，獲得目標圖；確定目標圖中與查詢圖匹配的子圖。應用本申請所提供的技術方案，可以高效地進行大規模圖數據的子圖匹配，提高信息查詢效率。本申請還公開了一種子圖匹配裝置、設備及存儲介質，具有相應技術效果。

技術領域

本申請涉及計算機應用技術領域，特別是涉及一種子圖匹配方法、裝置、設備及存儲介質。

背景技術

圖，是一種被廣泛應用的數據結構，適合用來描述具有內在關聯性且聯系緊密的數據。在許多應用領域中信息挖掘的問題都可以通過圖的相關理論和相應技術來解決，而子圖匹配技術作為實現圖數據上的能夠高效查詢的基本操作，也被廣泛的應用于各個領域和行業的實際問題中。例如社交網絡中的數據分析、互聯網中web鏈接的數據分析、生物數據的分析等等。

為了從已有的數據中挖掘出更有價值的東西，對于能在圖數據中進行查詢的子圖匹配方法的研究的關注越來越多。隨著數據量的爆發式增長，如何高效地進行大規模圖數據的子圖匹配，是目前本領域技術人員急需解決的技術問題。

發明內容

本申請的目的是提供一種子圖匹配方法、裝置、設備及存儲介質，以高效地進行大規模圖數據的子圖匹配。

為解決上述技術問題，本申請提供如下技術方案：

一種子圖匹配方法，包括：

根據預設的查詢規則構建查詢圖，所述查詢圖為一層或多層樹結構，包括多個查詢節點，每個查詢節點具有各自的節點類型，查詢節點之間的邊表示查詢節點間關系；

根據所述查詢圖的各查詢節點類型和查詢節點間關系，對原始圖進行點邊過濾處理，獲得目標圖；

確定所述目標圖中與所述查詢圖匹配的子圖。

在本申請的一種具體實施方式中，所述根據所述查詢圖的各查詢節點類型和查詢節點間關系，對原始圖進行點邊過濾處理，獲得目標圖，包括：

根據所述查詢圖的各查詢節點類型，將原始圖中不具有相應節點類型的節點過濾掉；

根據所述查詢圖的查詢節點間關系，將所述原始圖中不具有相應節點間關系的節點過濾掉；

將過濾后的所述原始圖確定為目標圖。

在本申請的一種具體實施方式中，所述確定所述目標圖中與所述查詢圖匹配的子圖，包括：

將所述查詢圖的層數確定為迭代輪數N，并初始化所述目標圖中每個目標節點的局部匹配狀態信息，N為正整數；

在第一輪迭代中，針對所述目標圖中的每個目標節點，將該目標節點與所述查詢圖中的根節點進行匹配，如果匹配成功，則更新該目標節點的局部匹配狀態信息，并將該目標節點更新后的局部匹配狀態信息發送給該目標節點的所有鄰居節點；

在第n輪迭代中，針對所述目標圖中的每個目標節點，如果該目標節點接收到該目標節點的鄰居節點發送的局部匹配狀態信息，則基于接收到的局部匹配狀態信息，將該目標節點與所述查詢圖中的第n層相對應的查詢節點進行匹配，如果匹配成功，則更新該目標節點的局部匹配狀態信息，將該目標節點更新后的局部匹配狀態信息發送給該目標節點的除向該目標節點發送信息的鄰居節點外的其他所有鄰居節點，n＝2,3,…,N-1；

在第N輪迭代中，針對所述目標圖中的每個目標節點，如果該目標節點接收到該目標節點的鄰居節點發送的局部匹配狀態信息，則基于接收到的局部匹配狀態信息，將該目標節點與所述查詢圖中的第N層相對應的查詢節點進行匹配，如果匹配成功，則更新該目標節點的局部匹配狀態信息；