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

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

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

生成樹(shù),圖G