基于協(xié)同邊推導(dǎo)的動(dòng)態(tài)流式圖并行抽樣算法.pdf

1、隨著應(yīng)用不斷深入，在社交網(wǎng)絡(luò)服務(wù)、科學(xué)計(jì)算仿真等場景中，圖數(shù)據(jù)持續(xù)、大量產(chǎn)生，對(duì)其進(jìn)行快速、有效分析具有十分重要的意義。在某些對(duì)精確度要求不是很高或者只要求反映部分關(guān)鍵圖特性的應(yīng)用中，采取從原圖中抽取具有代表性的子圖進(jìn)行分析的方法，能節(jié)省計(jì)算資源和提高處理效率。對(duì)動(dòng)態(tài)圖抽樣時(shí)，原圖的持續(xù)變化導(dǎo)致抽樣過程中無法獲取全圖靜態(tài)數(shù)據(jù)，故通常采用流式的抽樣算法。不過流式抽樣算法由于累計(jì)迭代特性，抽樣過程必須串行，因此當(dāng)抽樣子圖規(guī)模較大時(shí)，抽樣過程

2、減速嚴(yán)重，難以保證實(shí)時(shí)性，而若抽樣子圖偏小，則難以保證其與原圖相似。現(xiàn)有并行抽樣算法針對(duì)的都是靜態(tài)圖，不適用于動(dòng)態(tài)圖，因此需要提出一種并行的流式抽樣算法。
　　研究分析典型的流式圖抽樣算法PIES(Partial-Induce Edge Sampling)及其改進(jìn)算法 PIES-INV，分析 PIES并行化方案存在的問題，提出了一種基于協(xié)同邊推導(dǎo)的動(dòng)態(tài)流式圖并行抽樣算法PaStS(Parallel Streaming Sampli

3、ng)。PaStS與PIES-INV采取相同的暫存點(diǎn)替換策略，在并行抽樣時(shí)，利用全局點(diǎn)信息同步的機(jī)制實(shí)現(xiàn)動(dòng)態(tài)調(diào)整各抽樣器的抽樣目標(biāo)大小，以及實(shí)現(xiàn)基于全局點(diǎn)集的協(xié)同邊推導(dǎo)，從而解決流式抽樣算法并行化時(shí)點(diǎn)和邊大量減少的問題。
　　經(jīng)過在真實(shí)動(dòng)態(tài)圖數(shù)據(jù)集和生成圖數(shù)據(jù)集上的測試，PaStS算法相比PIES，在并行度為8時(shí)抽樣效率能提高15到49倍。PaStS抽樣得到的子圖在四種圖特性的代表性上與PIES-INV比較接近，在多數(shù)情況下都比P