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

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

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

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

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