[發明專利]海量圖數據上的路徑模式查詢系統

有效

• 申請號: 201310222168.2
• 申請日: 2013-06-05
• 公開（公告）號: CN103279543B
• 公開（公告）日: 2017-05-17
• 發明（設計）人: 王朝坤;白易元
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京匯信合知識產權代理有限公司11335
• 代理人: 夏靜潔

技術領域

本發明涉及海量圖數據查詢技術領域，尤其是涉及一種海量圖數據上的路徑模式查詢系統。

背景技術

現代社會中，圖的應用越來越廣泛，數據的管理技術已被廣泛應用于各個領域。其中互聯網、社交網絡、生物信息學等領域，對海量圖數據的高效管理有著很高的需求。如何有效的管理和應用這些大圖數據成為當前本領域技術人員所面臨的極大挑戰。

當今隨著信息技術的發展和社交網絡的興起，圖數據管理技術已成為數據管理領域的研究熱點之一。圖數據集上的高效查詢處理技術，尤其是海量規模圖數據上的查詢處理，成為解決社交網絡分析等大數據時代典型應用的重要基礎。

許多高效的圖查詢算法都直接或間接地依賴于兩個節點之間特定模式路徑的高效計算，例如，GraphGrep子圖查詢處理算法需要檢索所有的長度不大于L的路徑；化合物分類算法需要統計帶有特定標簽的路徑；社交網絡分析算法中，需要找出邊的顏色符合給定正則表達式的路徑。這類問題統稱為路徑模式查詢處理，或路徑模式匹配，是圖數據管理和挖掘中的一項基本操作。

正則表達式在文本模式匹配領域有很廣泛的應用，其強大的表達能力使之同樣適用于定義圖的路徑模式。它能夠在純文本表達式中表達各種約束和成員的重復模式。因此，本文使用正則表達式定義路徑模式，稱為圖的正則路徑模式。

現有一些圖查詢語言雖然支持正則路徑查詢，但是都存在一定不足。例如，GraphQL只支持有限的正則表達式。SPARQL只支持語義網絡數據，難以直接擴展到通用的圖數據中。近些年也出現了一些原生圖數據庫管理系統，如Neo4j、Apache Giraph，但它們仍然存在一些問題：Neo4j是一個具有強一致性的數據庫系統，在大型的分布式環境中性能較差；Giraph不支持高級查詢語言，并非一個成熟完整的圖數據管理系統。

因此，當下需要迫切解決的一個技術問題就是：如何能夠提出一種有效的措施，已解決現有技術中存在的問題。

發明內容

本發明所要解決的技術問題是提供一種海量圖數據上的路徑模式查詢系統，極大地方便了用戶查詢海量圖數據，且很大程度上提高海量圖數據的查詢執行計劃。

為了解決上述問題，本發明公開了一種海量圖數據上的路徑模式查詢系統，包括數據存儲服務模塊、數據更新服務模塊、協調服務模塊、查詢管理服務模塊和并行計算服務模塊，其中，所述數據存儲服務模塊，用于將圖數據存儲在分布式集群上，并為其他模塊提供數據讀取功能；所述數據更新服務模塊，將更新的日志合并到數據文件中；所述協調服務模塊，用于在計算過程中，協調服務負責機器間狀態的同步；所述查詢管理服務模塊，用于對內管理各個成員機器，并進行查詢的預處理、查詢任務的分發，查詢結果的收集；所述并行計算服務模塊，用于實際執行查詢的服務。

進一步地，所述查詢管理服務模塊對外是一個集中式的查詢接口，用于提供查詢接口、數據更新接口以及會話管理的功能。

進一步地，所述數據存儲服務模塊使用HDFS分布式文件系統完成圖數據的存儲。

進一步地，所述數據更新服務模塊是基于MapReduce構建將更新的日志合并到數據文件中的。

綜上，本方案能夠高效并行執行G-Path查詢，與大多數現有圖數據管理系統兼容，極大地方便了用戶查詢海量圖數據，且很大程度上提高海量圖數據的查詢執行計劃。

附圖說明

圖1是本發明的海量圖數據上的路徑模式查詢系統的結構示意圖；

圖2是本發明具體實施方式中所述的錯誤！未找到引用源。中所示的查詢自動機的例子示意圖；

圖3是本發明具體實施方式中所述的數據集的一個模型圖示意。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，下面結合附圖與實例對本發明作進一步詳細說明。但所舉實例不作為對本發明的限定。