[發明專利]大圖數據庫中基于集合相似度的子圖匹配方法

在審

• 申請號: 201710150451.7
• 申請日: 2017-03-14
• 公開（公告）號: CN107085594A
• 公開（公告）日: 2017-08-22
• 發明（設計）人: 洪亮;鄒磊
• 申請（專利權）人: 武漢大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 湖北武漢永嘉專利代理有限公司42102
• 代理人: 唐萬榮,李丹

1.一種大圖數據庫中基于集合相似度的子圖匹配方法，其特征在于，包括以下步驟：

1)在查詢圖的多個支配集中選取一個有效率的支配集，所述有效率的支配集包含最少的支配頂點數，且每個支配頂點的候選點數是最少的；

2)集合相似度剪枝：運用集合相似度剪枝方法得到查詢頂點的所有候選點；

3)結構剪枝：根據查詢圖Q同構的結構限制，對查詢頂點的所有候選點基于結構剪枝，過濾查詢頂點的候選點；

4)基于支配集的子圖匹配：

4.1)將查詢圖Q轉化為支配查詢圖；

4.2)在數據圖G中找出支配查詢圖的所有匹配，即Q^D和G的子圖間的映射M(Q^D)；

4.3)找出查詢圖Q的所有子圖匹配：將每個支配查詢圖Q^D的匹配擴展為查詢圖Q的子圖匹配；

如果當前狀態M(s)覆蓋了Q的所有頂點，則按照當前狀態M(s)輸出映射M(Q)；

否則，對每個未覆蓋的非支配頂點u′，考慮u′的1-hop和2-hop的鄰近支配頂點，然后檢查是否有候選對(u′,v′)滿足集合相似度的子圖匹配的條件，若是，則該候選對添加到當前狀態中；遍歷結束后，按照當前狀態M(s)輸出映射M(Q)。

2.根據權利要求1所述的子圖匹配方法，其特征在于，所述步驟1)中選取一個經濟的支配集包括以下步驟：

1.1)運用Branch and reduce從未被選擇的查詢頂點中迭代地選擇一個擁有最少候選點數的查詢頂點u；

1.2)利用Hash Sampling方法估算查詢頂點u的候選點數；

1.3)根據步驟1.1)和1.2)的結果選出經濟的支配集。

3.根據權利要求1所述的子圖匹配方法，其特征在于，所述步驟2)中集合相似度剪枝包括以下步驟：

2.1)從經濟的支配集包含的頂點集中挖掘密集頻繁模式，基于所有的1-頻繁模式和密集k-頻繁模式構建格，其中k≥2；

2.2)根據格中的頻繁模式構建倒排模式格；遵循以下原則：倒排模式格中的同一層的頻繁模式有相同的規模，且在k層的規模為k；

2.3)運用集合相似度剪枝方法得到查詢頂點的所有候選點；對查詢頂點u，首先運用垂直剪枝和橫向剪枝來過濾出位置錯誤的模式并確定倒排模式格中應當被掃描的點，然后使用廣度優先搜索對其進行遍歷，對每個被掃描的點P，進行反單調剪枝，獲得最終結果。

4.根據權利要求3所述的子圖匹配方法，其特征在于，所述步驟2.1)中將所有密集k-頻繁模式P按supp(P)的值倒序排列，并選擇前個模式，基于所有的1-頻繁模式和選出的密集k-頻繁模式構建格；其中supp(P)為支持P的元素集的數量，M為設定的格的規模，|F₁|為1-頻繁模式的集合中元素的個數。。