大規(guī)模圖增量迭代處理技術(shù)的研究與實(shí)現(xiàn).pdf

1、社交網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)和信息技術(shù)的快速發(fā)展，使圖論及其相關(guān)算法的應(yīng)用日益廣泛。其中，利用云計(jì)算環(huán)境開(kāi)發(fā)大規(guī)模圖的增量迭代處理平臺(tái)，已經(jīng)成為當(dāng)前學(xué)術(shù)界和工業(yè)界研究的熱點(diǎn)。但是針對(duì)數(shù)據(jù)劃分、磁盤(pán)管理和網(wǎng)絡(luò)通信等方面的優(yōu)化工作，相對(duì)較少，而這三個(gè)方面正是影響大圖處理平臺(tái)運(yùn)行效率的至關(guān)重要的因素。由于大圖的增量迭代處理，具有數(shù)據(jù)耦合性強(qiáng)、迭代頻率高、數(shù)據(jù)訪問(wèn)局部性差等特點(diǎn)，因此對(duì)于上述三個(gè)方面的優(yōu)化處理是一個(gè)十分具有挑戰(zhàn)性的課題，這也是本文的主

2、要工作內(nèi)容。
　　本文在數(shù)據(jù)劃分方面，首先分析了DFS生成圖和BFS生成圖的局部性，然后提出了連續(xù)劃分策略。相比于現(xiàn)有的隨機(jī)Hash劃分，連續(xù)劃分策略能夠保留輸入圖的原始局部性，避免數(shù)據(jù)劃分階段的全局洗牌操作，均衡計(jì)算負(fù)載。同時(shí)，為提供迭代過(guò)程的消息路由尋址服務(wù)，本文提出了基于Hadoop的圖頂點(diǎn)連續(xù)編碼方案和基于DHT的Hybrid-MT連續(xù)編碼方案，可以將圖頂點(diǎn)字符串轉(zhuǎn)換為數(shù)字連續(xù)編號(hào)。在磁盤(pán)管理方面，通過(guò)分析增量迭代過(guò)程，本

3、文提出了圖狀態(tài)轉(zhuǎn)換模型，并據(jù)此設(shè)計(jì)了基于列存儲(chǔ)模型的靜態(tài)Hash索引和基于Markov模型的動(dòng)態(tài)可調(diào)Hash索引。前者可以提高消息數(shù)據(jù)與本地圖數(shù)據(jù)之間連接操作的局部性，避免隨機(jī)磁盤(pán)存取。后者在前者基礎(chǔ)上，根據(jù)迭代狀態(tài)的轉(zhuǎn)換和Markov代價(jià)收益評(píng)估模型，可以動(dòng)態(tài)調(diào)整Hash桶的分割粒度，最小化磁盤(pán)存取開(kāi)銷。在網(wǎng)絡(luò)通信方面，通過(guò)擴(kuò)展BSP模型(Bulk Synchronous Parallel)，提出了基于EBSP模型的Hybrid迭代機(jī)

4、制，即圖數(shù)據(jù)同步處理，而消息數(shù)據(jù)跨步處理。特別的，消息跨步剪枝(ASMP)和跨步合并(ASMC)是兩種跨步處理方法，可以分別剪枝消息規(guī)模和加速消息傳播速度。此外，在連續(xù)劃分基礎(chǔ)上，本文提出了VCCP(Vertex-Cut basedon the Continuous Partitioning)方法，利用BFS生成圖的原始局部性，VCCP通過(guò)較低的預(yù)處理開(kāi)銷，能夠顯著改善總體運(yùn)行效率。最后，設(shè)計(jì)了DiterGraph原型系統(tǒng)，通過(guò)大量實(shí)驗(yàn)