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處理的需求，應該可以組成另外一種不同方式的應用。

Building a high-level dataflow system on top of Map-Reduce the Pig experience

Summary:
作者們在這篇中提出了一個簡單、且明確的dataflow的programming model。Pig這個model是一個high-level dataflow system，其切中了一個介於SQL和map-reduce之間的甜蜜點。其擁有類似SQL的high-level data manipulation，而靠此特性可以整合成有明確的dataflow客制化map和reduce function。
而由於map-reduce簡單的特性，會導致以下的問題:
1. 沒有辦法直接的去support N-step dataflow, 但這個需求在實際上卻很常見。
2. Map-reduce也缺少了給予combined processing of multiple datasets一個明確的support。
3. 一些需要頻繁的去抓取data的運作，像是filter、aggregation、top-k thresholding等等都必須要用人工去coding。
以上的問題會導致data analysis的速度，也會造成某些錯誤，或是使得data processing program變得難以閱讀。
作者提供了一個有著SQL精神的可組合式高階data manipulation constructs，同時又保留了map-reduce某些吸引人的特性，提出了Pig這個系統。
而在performance的部分，作者也提出了和map-reduce比較的數據，目前是需花費較純粹map-reduce多出50%的運算時間，但是這個可以視為一個介於code development/maintenance effort和執行時間之間的取捨。

Describable Visual Attributes for Face Verification and Image Search

Summary:
作者提出了一個利用attribute的classifier來作有關face verification的方法，並可以用這個方法拓展到face search等應用，其作法如下:
利用OKAO face detector可以將網路上取得的圖片作處理，可以將臉的角度、眼和嘴的角給抽取出來，之後再利用Amazon Mturk來作一個媒合指定labeling的工作，如此一來就可將每張圖的attribute給選定出來。
作者將臉部定義出10個region，包含1個全臉的區域及9個子區域，並在每個region中抽取中low level feature，而feature則是利用不同的pixel value types；不同的normalization方法；與不同的aggregation方式來湊出不同種類的feature。有了這些feature之後，作者使用了一個forward feature selection的方式，將每個不同的attribute classifier給train出來，使用的是RBF kernel的SVM，給定每個attribute 500個positive example和2000個negative example就可將所需的classifier給train好了。文中也呈現了其產生的數據，在73個attribute classifier中都有很好的正確率。
作者還提出了一個simile classifier的作法，是將一個人的10個區域給選出來之後，透過和上方所提的training方式相同選出最適合的8個區域與6種feature type，對於每個人共train出48個classifier。
有了以上這些資料之後，給定兩張input image，先經過face & fiducial detector，再經過一個affine alignment，之後再利用上述兩種classifier就可算出一連串的output，比對那些output就可以決定這兩張input image所指出的是不是同一個人了。
因為training的過程中所標記的其實是一個個attribute，每個attribute都是具有實際上的意義的，如亞洲人、高加索人、黑髮、金髮等等，故可以在image search上作為一個很好的輔助。再輸入一個query如:”dark-haired people with sunglass”就可以透過” dark-haired”和”sunglass”找出很符合要求的照片了，在此一架構下，搜尋的方式便很直覺的變成了我們平常要找東西時習慣用文字來描述的概念。

Comment:
這篇提出了一個很好的方法去做face verification和image search的工作。很重要的一個貢獻他不像LBP那樣每個特定的feature其實並不知道實際上有什麼意義，而在此的classifier所選定出來的feature代表的即是一個特定attribute，相較起來跟人類的想法較為接近。