本文關鍵詞：分布式環(huán)境下海量圖數據的可達性查詢研究

  更多相關文章： 分布式計算 可達性查詢 圖劃分 可達性索引

【摘要】：圖數據信息的應用極其廣泛,存在于科學技術的各個領域,因此經常會遇到圖數據信息中有關可達性查詢的計算問題。隨著數據量的急劇增長,傳統(tǒng)的可達性計算方法已經無法滿足大型圖數據上的計算,這使得如何在大型圖數據上進行可達性查詢成為了一個亟待解決的問題。圖數據的可達性查詢與其計算模型及處理算法密切相關。傳統(tǒng)的可達性計算方法存在本地局限、處理數據量不足及擴展性差等缺點,其改良算法在百萬級別頂點的圖數據上也有限制,只適用于在單機環(huán)境中進行計算。針對海量圖數據的可達性問題,設計了在分布式環(huán)境下海量圖數據的可達性計算框架,提供了一種可以對千萬級頂點和億級邊的圖數據進行可達性查詢的方法。針對于傳統(tǒng)的可達性方法無法有效地處理分布式海量圖數據的問題,設計了基于分布式文件系統(tǒng)的海量圖數據的可達性計算框架。計算框架中對圖進行了預處理,并設計了在分布式環(huán)境下針對可達性查詢問題的均衡拓撲劃分策略,經過一次劃分使得子圖內部擁有較好的內聚性;設計了分布式跨子圖索引,在子圖上找出骨干頂點和外部聯系頂點建立索引,用于有效地在劃分后的子圖內部和子圖之間進行并行的可達性查詢計算。通過圖劃分以及可達性連接測試表明,利用海量圖數據的可達性計算框架,可以有效地對分布式下千萬級頂點和億級邊的圖數據進行可達性查詢。
【學位授予單位】：華中科技大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5;TP391.3

【參考文獻】

中國期刊全文數據庫 前1條

1 鄭麗麗;;圖劃分算法綜述[J];科技信息;2014年04期

，

本文編號：1304730