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

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

U Kang, Charalampos E. Tsourakakis, Christos Faloutsos
SCS, Carnegie Mellon University
ICDM'09
======================================================

這篇最要是在探討 PEGASUS這個 peta graph mining library 對 peta-scale 資料的處理
其中提到了很多graph mining operations, ex: PageRank, diameter 等
都可以用GIM-V(Generalized Iterated Matrix-Vector)來解決

GIM-V 就是一個matrix 乘上一個vector (答案淺而易見也是一個vector)
這中間的步驟分為三個部分
1. combine2: 兩個element 相乘  (就是做一次乘法)
2. combineAll: 把n個乘法的結果全部加起來 (n-1個加法)
3. assign: 把算好的值填回去
利用這樣的架構之下，要平行來處理就變得很容易
因為在distributed system是用 <key, value> 這樣的pair來運作
combine2() 可以平行來算
算好之後全部由combineAll()來加總，每個row都要作一次combineAll()
但row之間是互相獨立來運算，所以也很容易平行
assign的值每個都是獨立的，也很容易平行

paper後面就介紹怎樣用SQL語法來做到GIM-V  (看來SQL對database真的很重要)
然後再透過GIM-V來實作
1. PageRank
2. Random Walk with Restart
3. Diameter Estimation
4. Connected Components
其實很明顯上面四件事幾乎都是search engine要做的事
也因此才會用到這樣peta-scale的data mining

後面就做了一些實驗來跟baseline (naive method) 比較
從time 跟 space 上面來分析  他們所提出的fast GIM-V 至少快了5倍

======================================================

優點：
1. 利用GIM-V來作比較
    像這樣large-scale data mining 要如何來比較真的很困難
    作者能夠想到利用這樣的方式，然後再証明一些運算(ex: PageRank)
    都能透過這樣的方法來解，提供一種比較的基準，是最大的賣點
2. 提出 fast GIM-V 比naive 方法快了5倍，這部分比較像演算法，寫得很詳細
3. 真的實作且實驗在large-scale data上  (1.5Pb & 120Gb)
    之前應該沒有人實驗這麼large-scale 的data