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

  更多相關(guān)文章： 分布式計(jì)算 可達(dá)性查詢 圖劃分 可達(dá)性索引

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

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

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

，

本文編號(hào)：1304730