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

有效

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

本發明公開了一種面向多模式圖匹配的并行加速方法。本方法為：1)生成目標領域的模式圖集的多模式圖索引；2)對所述多模式圖索引采用逐層分組策略，即對所述多模式圖索引中每一層出現的模式圖進行評估，得到該層中每個模式圖的匹配代價，然后根據匹配代價對該層的模式圖進行分組；3)對不同分組分別分配一線程同時進行匹配計算。本發明通過采用PatternTree索引構建算法挖掘模式圖間存在的結構相關性，對于結構相關性較弱的模式圖設計并行匹配策略進一步提升匹配性能。

技術領域

本發明提出一種面向多模式圖匹配的并行加速方法，屬于計算機軟件技術領域。

背景技術

在大數據時代，數據規模不斷擴大，數據結構日益復雜，數據間的關聯更加緊密，這些特點給大數據分析帶來巨大挑戰。圖作為一種廣泛應用的數據結構，可以有效刻畫緊密關聯的數據，眾多領域的實際問題都可以轉化為圖上的計算問題，例如圖像分析、生物數據分析、社交網絡分析、隱私保護等。圖模式匹配技術(Graph Pattern MatchingTechnology)通過對大規模圖數據上關聯關系的高效查詢，是解決上述復雜圖數據分析和挖掘問題的重要手段，它已成為近年來學術界和工業界廣泛關注的問題之一。

子圖同構(Subgraph Isomorphism)是圖模式匹配的一類基礎問題，對于給定的數據圖和模式圖，子圖同構算法實現在數據圖中查找與模式圖的結構和屬性完全一致的所有子圖。該問題屬于NP完全問題，眾多啟發式算法通過優化匹配順序、剪枝策略不斷提高匹配性能。近年來，隨著數據規模的擴大和硬件水平的提高，利用并行計算、GPU等方式優化匹配性能的技術方興未艾。而現有算法主要針對單模式圖匹配進行性能提升，將待匹配的模式圖看作獨立的目標實現匹配優化和性能評估。

然而在實際應用中，存在許多應用場景需要批量處理模式圖，例如，在網絡安全領域中，網絡可以按照以IP地址為結點，通信關系為邊，轉換為圖數據結構，將網絡中的各類攻擊事件抽象為模式圖，通過在通信網絡中實時匹配這些模式圖實現對網絡攻擊事件的監測；在社交網絡分析中，以用戶為結點，用戶間的好友關系、粉絲關系為邊構建社交關系網絡，關注的社團和人物可以用其所在的關系子網絡表示，通過圖模式匹配實現社團推薦、人物推薦等任務；在生物科學領域中，蛋白質結構本身就是一種圖結構，對于各類未知特性的蛋白質，研究者可以在已知功能特性的數據庫中搜索與其相似的結構，來推測其功能和特性。在上述應用中，需要同時匹配多個模式圖，這些模式圖間通常存在重復結構，而現有圖模式匹配算法主要針對單一模式圖進行處理，在處理批量模式圖匹配問題上，采用串行匹配策略，忽略了模式圖之間的結構相關性，造成了匹配過程中的大量冗余計算。

現有的圖模式匹配加速技術主要包括三個方面：基于數據圖索引的匹配加速技術、基于數據圖并行的匹配加速技術、基于GPU的匹配加速技術。基于數據圖索引的匹配加速技術主要通過挖掘數據圖中有辨別力的特征建立倒排索引，在匹配過程中首先通過索引快速縮小搜索空間，再對小規模的備選集合進行精確匹配，從而達到加速匹配的目的。基于數據圖并行的匹配加速技術，通過將數據圖劃分為若干子圖，采用多個計算節點對每部分數據子圖進行匹配計算，最后合并每個子圖的匹配結果，這類算法主要面臨兩個技術挑戰：一是如何均衡劃分數據圖，二是如何對匹配結果進行高效合并。基于GPU的匹配加速技術，充分發揮GPU的并行處理能力，將匹配計算量較大搜索剪枝部分由CPU遷移到GPU以提升整體匹配性能。

綜上所述，目前的圖匹配加速技術主要針對單一模式圖匹配問題從構建數據圖索引、劃分數據圖進行分布式計算、借助高性能GPU完成密集計算等角度實現匹配加速。然而，在處理多個模式圖時，現有算法仍將每個模式圖視為獨立個體采用串行策略進行匹配，其中存在不同程度的冗余計算。針對單個模式圖串行匹配存在冗余計算的問題，多模式圖匹配技術應運而生，該類技術的核心思想是基于模式圖間存在的結構關聯，挖掘存在于模式圖中的重復結構(子結構)，從而定義基于重復結構(子結構)的最優匹配策略，通過降低對相同結構的重復匹配提升匹配性能。但是現存多模式圖匹配技術還不夠成熟，對于結構相關性較弱的模式圖沒有高效的并行處理方式，多模式圖匹配技術的性能還有待提高。

發明內容