[發(fā)明專利]一種基于BSP模型的實時圖數(shù)據(jù)處理系統(tǒng)及方法

有效

• 申請?zhí)枺?/td>: 201310256296.9
• 申請日: 2013-06-25
• 公開（公告）號: CN103336808B
• 公開（公告）日: 2017-12-15
• 發(fā)明（設(shè)計）人: 周薇;韓冀中;戴嬌;張章
• 申請（專利權(quán)）人: 中國科學(xué)院信息工程研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京輕創(chuàng)知識產(chǎn)權(quán)代理有限公司11212
• 代理人: 楊立

1.一種基于BSP模型的實時圖數(shù)據(jù)處理系統(tǒng)，其特征在于，包括相互通信的數(shù)據(jù)存儲單元(1)、圖數(shù)據(jù)查詢統(tǒng)計單元(2)和圖數(shù)據(jù)分析處理單元(3)：

數(shù)據(jù)存儲單元(1)，其用于對圖數(shù)據(jù)進行預(yù)處理，并將預(yù)處理后的圖數(shù)據(jù)按“內(nèi)存存儲—分布式內(nèi)存存儲—分布式文件系統(tǒng)”的三層存儲結(jié)構(gòu)進行存儲，并基于圖數(shù)據(jù)生成作業(yè)；

圖數(shù)據(jù)查詢統(tǒng)計單元(2)，其用于對所述數(shù)據(jù)存儲單元(1)的圖數(shù)據(jù)進行查詢和統(tǒng)計，將所述數(shù)據(jù)存儲單元(1)生成的作業(yè)分解為多個任務(wù)，并將分解的任務(wù)以均衡的方式分發(fā)給相應(yīng)計算節(jié)點，再統(tǒng)計每個任務(wù)的計算結(jié)果，并合并所有任務(wù)的計算結(jié)果作為最終結(jié)果返回給用戶；

圖數(shù)據(jù)分析處理單元(3)，其用于使各計算節(jié)點通過迭代計算執(zhí)行所述圖數(shù)據(jù)查詢統(tǒng)計單元(2)分解出的任務(wù)，并通過消息傳遞實現(xiàn)每次迭代計算的同步，并輸出任務(wù)的計算結(jié)果至所述圖數(shù)據(jù)查詢統(tǒng)計單元(2)；

所述圖數(shù)據(jù)分析處理單元還包括消息傳遞同步機制，其用于通過消息傳遞實現(xiàn)每次迭代計算的同步。

2.根據(jù)權(quán)利要求1所述的實時圖數(shù)據(jù)處理系統(tǒng)，其特征在于，所述數(shù)據(jù)存儲單元(1)包括預(yù)處理模塊(11)、導(dǎo)入模塊(12)和存儲模塊(13)；

所述預(yù)處理模塊(11)，其連接所述導(dǎo)入模塊(12)，用于遍歷源數(shù)據(jù)，并對源數(shù)據(jù)中的點邊關(guān)系進行處理，并將處理后的源數(shù)據(jù)傳輸給所述導(dǎo)入模塊(12)；

所述導(dǎo)入模塊(12)，其連接所述存儲模塊(13)，用于將源數(shù)據(jù)轉(zhuǎn)化為簡單圖與超圖相結(jié)合的圖數(shù)據(jù)格式，并存入所述存儲模塊(13)中；

所述存儲模塊(13)，其用于按“內(nèi)存存儲—分布式內(nèi)存存儲—分布式文件系統(tǒng)”的三層存儲結(jié)構(gòu)存儲圖數(shù)據(jù)，并將圖數(shù)據(jù)生成作業(yè)傳輸給所述圖數(shù)據(jù)查詢統(tǒng)計單元。

3.根據(jù)權(quán)利要求1所述的實時圖數(shù)據(jù)處理系統(tǒng)，其特征在于，所述圖數(shù)據(jù)查詢統(tǒng)計單元(2)包括作業(yè)分解模塊(21)和作業(yè)合并模塊(22)；

所述作業(yè)分解模塊(21)，其用于將所述數(shù)據(jù)存儲單元生成的作業(yè)分解為多個任務(wù)，并將分解的任務(wù)以均衡的方式分發(fā)給相應(yīng)計算節(jié)點執(zhí)行，實現(xiàn)每個計算節(jié)點上的負載均衡；

所述作業(yè)合并模塊(22)，其用于統(tǒng)計每個任務(wù)的計算結(jié)果，并合并所有任務(wù)的計算結(jié)果作為最終結(jié)果。

4.根據(jù)權(quán)利要求1所述的實時圖數(shù)據(jù)處理系統(tǒng)，其特征在于，所述圖數(shù)據(jù)分析處理單元(3)包括計算模塊(31)、通訊模塊(32)和輸出模塊(33)；

所述計算模塊(31)，其連接所述通訊模塊(32)，用于通過迭代算法計算各節(jié)點范疇內(nèi)的圖數(shù)據(jù)，并通過消息傳遞實現(xiàn)每次迭代計算的同步，再將計算結(jié)果傳輸給該節(jié)點對應(yīng)的通訊模塊(32)；

所述通訊模塊(32)，其連接所述計算模塊(31)，用于將計算結(jié)果傳送給其余節(jié)點的計算模塊(31)重新進行計算；

所述輸出模塊(33)，其連接所述計算模塊(31)，用于輸出最終的計算結(jié)果。

5.一種基于BSP模型的實時圖數(shù)據(jù)處理方法，其特征在于，包括：

步驟1，預(yù)處理圖數(shù)據(jù)，并將預(yù)處理后的圖數(shù)據(jù)按“內(nèi)存存儲—分布式內(nèi)存存儲—分布式文件系統(tǒng)”的三層存儲結(jié)構(gòu)進行存儲，再基于圖數(shù)據(jù)生成作業(yè)；

步驟2，查詢和統(tǒng)計存儲的圖數(shù)據(jù)，將生成的作業(yè)分解為多個任務(wù)，并將分解的任務(wù)以均衡的方式分發(fā)給相應(yīng)計算節(jié)點進行計算；

步驟3，各計算節(jié)點通過迭代計算執(zhí)行分解出的任務(wù)，并通過消息傳遞實現(xiàn)每次迭代計算的同步，并輸出每個任務(wù)的計算結(jié)果；

所述步驟3中通過消息傳遞實現(xiàn)每次迭代計算的同步具體包括：

步驟3B1，在生成圖數(shù)據(jù)時，記錄圖數(shù)據(jù)的點邊聯(lián)系，作為控制消息，并基于控制消息生成任務(wù)拓撲結(jié)構(gòu)；

步驟3B2，任務(wù)源向任務(wù)終點發(fā)送控制消息，任務(wù)終點對控制消息進行匹配；

步驟3B3，根據(jù)任務(wù)終點對控制消息的匹配結(jié)果，任務(wù)源向相應(yīng)的任務(wù)終點發(fā)送數(shù)據(jù)消息；

步驟3B4，控制消息和數(shù)據(jù)消息接收完全后，進入下一個迭代過程；

步驟3B5，根據(jù)上次迭代中終結(jié)的頂點，提取出與這些頂點連接的其他任務(wù)的頂點，并用上次迭代的控制消息減去這些頂點，形成新的控制消息；

步驟3B6，根據(jù)新的控制消息，重復(fù)步驟3B2至步驟3B5；

步驟4，統(tǒng)計每個任務(wù)的計算結(jié)果，并合并所有任務(wù)的計算結(jié)果作為最終結(jié)果返回給用戶。