[發明專利]一種圖數據存取方法及系統

在審

• 申請號: 201510028305.8
• 申請日: 2015-01-20
• 公開（公告）號: CN104615677A
• 公開（公告）日: 2015-05-13
• 發明（設計）人: 劉琴;朱宏明;楊曉雯;周游;張旎
• 申請（專利權）人: 同濟大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海光華專利事務所 31219
• 代理人: 余明偉

技術領域

本發明涉及一種計算機技術，特別是涉及一種圖數據存取方法及系統。

背景技術

圖是計算機科學中最常用的一類抽象數據結構，在結構和語義方面比線性表和樹更復雜，在數據與數據關系上更具有一般性表示能力。雖然圖的應用和處理技術已經發展了很長時間，但隨著信息規模的不斷增長，圖的規模日益擴大，如何對大規模圖進行高效處理成為新的挑戰。目前采用云計算環境進行大規模圖的存儲和處理具有優勢。基于云計算環境的圖存儲系統大致可分為兩種：一種是以GFS、HDFS為代表的分布式文件系統；另一種是以BigTable、Hbase為代表的NoSQL分布式數據庫。

具體來說，以HDFS為代表的分布式文件系統提供了一個統一的文件系統視圖，并通過將圖頂點、邊數據作為文件直接存放。但對圖數據的管理依賴于人工或半自動的數據管理，雖具有強大的存儲能力，但數據管理效率較低。另一方面，NoSQL數據庫采用的數據模型主要有文檔存儲、列族存儲、Key-Value存儲模型、圖存儲模型。文檔存儲模型與分布式文件系統類似，比較適合存儲系統日志等非結構化數據，但不太適合以鄰接矩陣、鄰接表組織的圖數據，其將數據作為統一的文檔形式存儲，為支持靈活性導致的處理效率的降低也會成為大規模圖數據管理的性能瓶頸。列族存儲模型比較適合對某一列進行隨機查詢，但是對于窮舉式遍歷，反而不如傳統的面向行的存儲模式。與上述存儲模型相比，Key-Value模型通過將數據組織為主鍵-數據的映射關系，非常適合通過主鍵進行查詢和遍歷，但對復雜的條件查詢支持度不高。因此，Key-Value模型可很好地支持通過id為條件的單個頂點查詢或圖遍歷操作，但對某個屬性的檢索只能通過全表掃描完成，性能不高。在實際運用中，應用對圖存儲的要求不僅僅局限于對單個節點的數據獲取，而是對圖的拓撲結構，如最短路徑、連通性等具有檢索要求，而在這方面Key-Value則不能很好地支持。

最后，圖存儲模型的相關研究還不完善，只有少數分布式圖數據庫如Neo4j等采用了圖存儲模型。這種模型由于其本身的適配性能很好地支持對圖拓撲結構的檢索，但很多時候需要對整個圖做計算才能得出需要的信息，而且這種結構不太好做分布式的集群方案，典型模型如Neo4j不能保持與已有云計算環境如Hadoop的兼容性，從而不能很好地利用云計算環境的可擴展性、容錯性等方面的特性。

鑒于此，如何找到一種方法提高對大量圖數據信息的存取性能成為了本領域技術人員亟待解決的問題。

發明內容

鑒于以上所述現有技術的缺點，本發明的目的在于提供一種圖數據存取方法及系統，用于解決現有技術中在云計算環境下對圖數據的存取性能不高的問題。

為實現上述目的及其他相關目的，本發明提供一種圖數據存取方法，所述圖數據存取方法包括：將待存儲的圖數據信息分成邊數據信息與頂點數據信息；其中，所述邊數據信息包括邊所連接的頂點標識符；所述頂點數據信息包括一個或多個頂點屬性信息，所述頂點屬性信息包括頂點屬性數據的定位信息以及頂點屬性解析信息的定位信息，所述頂點屬性數據的定位信息用于確定所述頂點屬性數據的位置，所述頂點屬性解析信息的定位信息用于確定所述頂點屬性解析信息的位置；所述頂點屬性解析信息用于對所述頂點屬性數據進行解析，以獲取所述頂點屬性的值；所述頂點屬性解析信息包括所述頂點屬性的類型以及所述頂點屬性在所述頂點屬性數據中的取值方式；分別存儲所述邊數據信息與所述頂點數據信息。

可選地，所述頂點屬性數據的定位信息包括標識符或指針的形式；所述頂點屬性解析信息的定位信息包括標識符或指針的形式。

可選地，所述頂點屬性解析信息還包括分隔符信息，所述頂點屬性數據以所述分隔符分割成多個頂點屬性列，所述頂點屬性的取值方式為：在所述頂點屬性在所述頂點屬性數據中相應順序的所述頂點屬性列中進行取值；當所述分隔符為空時，所述頂點屬性解析信息包括字節取值范圍，所述頂點屬性的取值方式為：在所屬頂點屬性數據的所述字節取值范圍中進行取值。

可選地，所述頂點屬性的取值方式還包括對所述頂點屬性數據中獲取的值進行進一步解析處理，所述進一步解析處理包括計算平均值。

可選地，所屬頂點屬性解析信息以XML格式定義。

可選地，所述圖數據存取方法還包括：讀取所述圖數據的邊數據信息；通過所述邊數據信息的頂點標識符定位所述頂點數據信息；讀取所述頂點數據信息，根據所述頂點屬性解析信息對所述頂點屬性數據進行解析，獲取所述頂點數據信息的頂點屬性值。