分布式大規(guī)模圖數(shù)據(jù)流式劃分算法FENNEL的改進(jìn).pdf

1、圖劃分在分布式計(jì)算和大規(guī)模圖數(shù)據(jù)處理等方面有著重大的意義。當(dāng)圖數(shù)據(jù)規(guī)模較小時，靜態(tài)圖劃分算法（如METIS）能有效處理，獲得較小的切邊率；但是隨著應(yīng)用快速發(fā)展，圖數(shù)據(jù)規(guī)模的急劇增長給靜態(tài)圖劃分算法造成顯著挑戰(zhàn)，因其處理速度及可擴(kuò)展性較差而難以處理千萬級以上大規(guī)模的流式圖數(shù)據(jù)。
　　流式圖劃分算法的出現(xiàn)很好的解決了上述問題。FENNEL算法對多種流式圖劃分算法進(jìn)行了統(tǒng)一的建模，其切邊率要優(yōu)于目前主流的流式圖劃分算法，且較為接近學(xué)術(shù)界

2、公認(rèn)優(yōu)秀的靜態(tài)圖劃分系統(tǒng)METIS，而其運(yùn)行速度卻比METIS快。不過，F(xiàn)ENNEL算法是一種串行的流式劃分算法，擴(kuò)展能力受限，如何提高其并發(fā)性而且減少因并發(fā)性提高而帶來的切邊率影響就成為改進(jìn)所面臨的主要挑戰(zhàn)。
　　本項(xiàng)研究通過對FENNEL的處理模型進(jìn)行分析，找出FENNEL現(xiàn)有分布式部署方法中，星形串行網(wǎng)絡(luò)模型存在的處理效率低、可擴(kuò)展性差等問題，并針對這兩方面的問題，提出了一種并發(fā)改進(jìn)方案，以及一種樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并進(jìn)行理論

3、推導(dǎo)，以求證其可改善系統(tǒng)并發(fā)性及擴(kuò)展性。然后，對各種類型的圖數(shù)據(jù)進(jìn)行串行、并發(fā)模型的對比測試，測試數(shù)據(jù)表明了在原生圖數(shù)據(jù)以及圖數(shù)據(jù)隨機(jī)到達(dá)的情況下，F(xiàn)ENNEL并發(fā)改進(jìn)方案可以保證幾乎不影響圖劃分切邊率，同時有效的加快圖劃分的速率，但是其速率會隨著工作節(jié)點(diǎn)數(shù)量的增加而減低；而樹形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能通過調(diào)整并發(fā)度來有效提高圖劃分速率，且其速率幾乎不會受到工作節(jié)點(diǎn)數(shù)量的影響。不過，對于按照廣度優(yōu)先搜索順序進(jìn)行預(yù)處理后的圖數(shù)據(jù)，即圖節(jié)點(diǎn)按照鄰接關(guān)