基于分布式存儲的大規(guī)模圖的深度優(yōu)先搜索算法研究

發(fā)布時間：2020-06-02 16:50

【摘要】：深度優(yōu)先搜索(DFS)是一種基本的圖操作,它以深度優(yōu)先的形式遍歷整個圖,而DFS對圖G中所有節(jié)點的搜索結(jié)果是一棵生成樹,稱為DFS-Tree。深度優(yōu)先搜索算法一直是計算機(jī)科學(xué)技術(shù)領(lǐng)域研究的熱點問題,廣泛應(yīng)用于連通分量計算、拓?fù)渑判�、社區(qū)檢測等。隨著大數(shù)據(jù)時代的來臨,數(shù)據(jù)規(guī)模不斷增大,數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)也越來越復(fù)雜,基于內(nèi)存的DFS算法無法適用于大規(guī)模圖數(shù)據(jù),無法滿足日益增長的數(shù)據(jù)規(guī)模和查詢傳輸有效率的需求。因此需要設(shè)計一個更加高效的低I/O的深度優(yōu)先搜索算法,運用于分布式存儲的大規(guī)模圖。本文深入研究了現(xiàn)有的深度優(yōu)先搜索的半外算法,它針對存在于磁盤上的圖G進(jìn)行I/O高效的深度優(yōu)先搜索。研究中發(fā)現(xiàn),雖然此類算法在一定程度上提高了I/O的效率,但是仍無法滿足分布式大規(guī)模圖存儲環(huán)境的下的高效I/O處理。對于分布式圖存儲時,半外算法得到關(guān)于圖G的生成樹及消除強(qiáng)連通時會伴隨著大量的I/O,并且當(dāng)原有數(shù)據(jù)存儲為廣度優(yōu)先搜索順序存儲時,子圖間存在著很多的橫向邊,導(dǎo)致算法效率下降。針對分布式存儲的圖G進(jìn)行深度優(yōu)先搜索時,設(shè)計高效I/O的劃分算法將是本文研究的主要方向和內(nèi)容。本文針對大規(guī)模圖分布式存儲特性,提出一種適用于分布式存儲的圖結(jié)構(gòu)的深度優(yōu)先搜索算法,對以DFS方式存儲和BFS方式存儲兩種存儲方式的圖結(jié)構(gòu)分別給出了相應(yīng)的解決策略。DS算法基于根節(jié)點建立全局關(guān)系圖,將原圖劃分成多個子圖,在各子圖內(nèi)再次建立局部關(guān)系圖,分別求得各個子圖的深度優(yōu)先搜索子樹,最后將處理過的子樹進(jìn)行歸并,快速建立I/O高效的深度優(yōu)先搜索樹。由于各個子圖區(qū)域間存在可到達(dá)關(guān)系,即橫向邊關(guān)系。本文采用上推方法,將各個子樹間暗含的關(guān)系傳遞到關(guān)系圖中,關(guān)系圖在一定的算法條件下進(jìn)行判斷并返回處理方法。對于BFS方式存儲的圖,站點間存在大量的聯(lián)系需要處理,本文在各個子區(qū)域分別求得子樹后,算法將對于不同類型的橫向邊進(jìn)行判斷并給出處理和連接方法。算法能夠有效減少內(nèi)外部I/O通信,提高I/O效率。最后,通過和傳統(tǒng)的分布式存儲的DFS算法的實驗結(jié)果進(jìn)行對比分析,證明本文提出的基于分布式存儲的大規(guī)模圖的深度優(yōu)先搜索算法具有較好的DFS效率。
【圖文】：

生成樹,圖G