PEGASUS - A Peta-Scale Graph Mining System Implementation and Observations

PEGASUS - A Peta-Scale Graph Mining System Implementation and Observations

Summary:
作者提出了一個GIM-V(Generalized Iterated Matrix-Vector Multiplication)的架構，擁有以下特性:
1. 可以在多台機器上來平行運算。
2. 提出了一個加速的方法，可以擁有比同樣架構non-optimized的情況下快五倍的運算速度。
3. 對於graph中的edge有linear running time。

GIM-V其演算法的核心想法如下，他把一個M x v = v’的矩陣相乘式分成三個operation:
(1) combine2: mij和vj相乘。
(2) combineAll:將n個在combine2相乘出來的結果(for node i)給相加起來。
(3) assign:將算好的vi’指定回原來的vi向量中。
而這個架構可以拆成一個兩個stage的工作，每個stage分別都是可以套入map-reduce的架構之中。這樣就可以用多台機器去平行處理一個矩陣乘法的工作。而此一架構，不只能夠解矩陣的乘法，還可以套用到如page-rank、random walk with restart、diameter estimation和connected component上。

將上述方法直接套用起來的話，就是文中所提到的GIM-V BASE版本，而之後作者提出了加速的一些版本，如GIM-V BL:以一個個bolck為基準，將矩陣M分解成一個N*N個b*b的小block，再把v分解成N個b維的向量，這樣就可將HADOOP中的主要瓶頸(shuffling stage where network transfer, sorting)給降低。而在資料壓縮的部分，因為透過這種方式可以將原本矩陣中每個元素都需要兩個4byte整數來儲存其位置，改由只要儲存block所在的位置就好，裡面每個元素總共只需要利用2xlogb的bit數來儲存，故在壓縮上效果也不錯。另外如GIM-V CL:他會先對矩陣M去作clustering，使得元素擺放的位置可以建構出一個擁有最多zero-block的M，如此一來由於全零的block不需要加入運算，就可以達到加速和資料壓縮的效果。還有GIM-V DI，像在找connected component的HCC演算法中，可以利用在一個block中先作多次處理的方式，使得最後須要運算的次數就變少了(即不需要多花時間在多次的map和reduce上)。

而作者在實驗的部分，也針對了現有的資料去作分析，即對wikipedia和yahoo的網頁等等去作分析，都可以對超大規模的資料去作處理。

Comment:
作者提出的架構雖然是在HADOOP架構上用map reduce的方法在多台機器上跑large scale data的處理，尤其是在矩陣運算上的有顯著的效果。此一架構說不定可以轉換至CUDA的平行運算上，雖然在個人電腦上可能不需要用到如此large-scale的處理，但是有些需要矩陣運算的功能可能會有要real-time處理的需求，應該可以組成另外一種不同方式的應用。