[aMMAI] Paper Summary: PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations

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

Author: U Kang, Charalampos E. Tsourakakis, Christos Faloutsos

Publication: ICDM 2009

這篇paper主要是在描述一個graph mining library, PEGASUS, 其中最重要的部分GIM-V (Generalized Iterated Matrix-Vector multiplication)

GIM-V最主要的概念:

假設有n*n的matrix M和大小為n的vector v，m_i,j 表示在M中(i,j)位置的值。

將兩者相乘，可用下面的數學式子表示

接著將它轉換成需要的graph mining algorithms

1. combine2: multiply mi,j and vj .

2. combineAll: sum n multiplication results for node i.

3. assign: overwrite previous value of vi with new result to make v′i.

接著paper就描述了許多mining的方法，都將它轉成GIM-V上述三個主要的operation，有PageRank、Diameter Estimation、Connected Components。

• GIM-V BASE: Naive Multiplication是每個將matrix裡面每個項目拆開下去做。
• GIM-V BL: Block Multiplication是將matrix中的資料切成一個個block去做，能加快速度的原因有二，一個是減少需要在shuffling步驟中排序的數量，二是資料的大小減少。
• GIM-V CL: Clustered Edges先對matrix內的值作分群，在切block去做，可以有效加快速度，但是要注意的是，必須是block base才有加速的效果，如果是每個項目分開去跑，事先分群並沒有意義。
• GIM-V DI: Diagonal Block Iteration:由於GIM-V的主要瓶頸在於shuffling與I/O。在HCC中利用與diagonal block相乘來減少迭代的次數。

時間複雜度分析，每次迭代所需要的時間為O( ((V+E)/M) log ((V +E)/M) )，空間消耗上，需要O(V+E)。

paper後面有利用GIM-V對實際的例子測試Connected Components、PageRanks、Diameter這三個mining演算法。

這篇paper主要的貢獻有

1.      提出了一個可以是用在很多mining算法的方法。

2.      GIM-V有很多最佳化的方式。

3.      有針對實際的例子作測試。

整體來說，內容寫得很詳細，每個它所提到的演算法都有一步步拆成GIM-V的形式，能達到最佳化的原因有用圖示說明比較清楚，最後也有實際做在真實世界上的實驗，很有說服力。

[aMMAI] Paper Summary: Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience

Title: Building a High-Level Dataflow System on top of Map-Reduce: The Pig Experience

Author: Alan F. Gates, Olga Natkovich, Shubham Chopra, Pradeep Kamath, Shravan M. Narayanamurthy, Christopher Olston, Benjamin Reed, Santhosh Srinivasan, Utkarsh Srivastava

Publication: VLDB 2009

Pig 是一個high-level的系統，有點像SQL一樣可以利用一些語法去控制資料。

隨著資料量越來越龐大，許多地方都使用Map-Reduce來處理資料，Pig像是一個中介，將所寫的語法轉成Map-Reduce可處理的job。

Map-Reduce programming model存在著一些問題。

1.      不支援N-step dataflow

2.      缺乏支援結合多個data set的processing

3.      一些基本的且常用的操作(ex. Filtering, aggregation)必須自己寫。

Pig使用Pig Latin作為輸入，將之轉成Map-Reduce job。

下面是整個處理過程的overview

Fig2 左邊就是使用者寫的Pig Latin，先將她轉為logical plan。

Pig提供了許多type可以使用，支援比較複雜的type: map、tuple、bag。

接著將Logical plan轉為physical plan。

上面的數字表示對應的步驟，其中JOIN與GROUP會對應的多個physical stage。

最後再將physical plan轉成map reduce plan。

Pig 提供了對nested sub-plan的處理，所以在physical多了SPLIT/MULTIPLEX的處理。因為使用者可能想對同一份資料作多項處理，但是並不想重複load data。

為了控制pipeline中的tuple，他們也考慮的push model和pull model。

由於Hadoop是用java開發，所以pig也用java開發，但是因為java無法直接對memory作處理，所以很容易造成memory不夠的問題。

一般解決的方式是用增加JVM memory大小。

此外，Pig也提供了UDF，使用者自訂的函式。

他們對每個STREAM建立兩個thread: 一個用來feeding data去執行，另一個用來consuming data，先queue起來。

  

這篇paper最主要應該是要解決Map-Reduce上的問題，以及提供一些high-level的控制方式，讓使用者可以更方便操作資料。

[aMMAI] Paper Summary: Describable Visual Attributes for Face Verification and Image Search

Title: Describable Visual Attributes for Face Verification and Image Search

Author: Kumar, Berg, Belhumeur, Nayar

Publication: PAMI, 2011

這篇paper利用visual attribute來做Face Verification和Image Search。

所以是針對人臉的attribute來training。

Attribute: 在這邊的意思是可以用來描述圖片的label。例如: 性別、年記等

Face Verification: 比對兩張臉是不是同一個人。

Image Search: 輸入attribute找出特定的臉。(例如: 戴眼鏡的男人。)

因為傳統作法都是取low level feature作training，往往會形成高維的資料，且對人來說感覺上並不直觀。所以希望改成用attribute base來改善。

他們用了兩個不同的attribute-base:

1. Describable visual attributes: 就是上面描述的性別、年記之類的

2. Similes: 與某個參考的人做比較。

建立資料庫:

1. 從網路上蒐及圖片，人工做tag。

2. 做人臉校正。

3. 因為是請網路上的人去標tag，所以必須去做驗證，看準確度夠不夠。

下圖是training的架構圖。

Learning visual attribute:

1. 如果是二分法的(如性別)，就真對性別train一個classifier，如果非二分法的(如年紀)，就真對不同的年紀範圍train不同的classifier。
2. 選一些適當的low level feature進來。
3. 利用SVMs with RBF kernel做分類。

下圖是利用train出來的attribute跟simile classifier作face verification的步驟。

由實驗果看出來，attribute base classifier的確有不錯的performance

這篇paper的好處:

• Attribute對人來說比較直覺。
• feature維度比較低比較有效率。
• 有提供應用的方法。
• 提供了兩個tag好的dataset，” FaceTracer”，” PubFig”。

[aMMAI] Paper Summary: Where’s Waldo: Matching People in Images of Crowds

Title: Where’s Waldo: Matching People in Images of Crowds

Author: Rahul Garg, Deva Ramanan, Steven M. Seitz, Noah Snavely

Publication: CVPR, 2011

這篇paper主要的目的就是想要在一大群照片中找出特定的人。

就跟Where’s Waldo這個遊戲一樣。

下面的圖是system overview

過程是這樣:

1. 使用者先輸入一大群的照片(必須是single event)。[圖上排最左]
2. 使用者要挑出一張照片，標出想要的人物(必須標出head, ground, 3 different part) 。[圖上排左邊數來第二]
3. 利用使用者標出的part training color model。使用color model的主要原因是因為圈出的人物可能會很小，以及解析度很低等問題，用SIFT之類的feature效果見得比較好。[圖上排右邊數來第二]
4. system註冊使用者輸入的照片，找出照片之間的相對3D空間位置，以及相機角度(by Model the world from Internet photo collections.)。[圖下排最左]
5. 利用步驟4找出的3D 相對位置找出可能的candidate location，利用前面train出來的appearance model算分數。[圖下排中間]
6. 最後加上contextual的資訊，建MRF model，來提高performance。[圖上排最右]

該篇paper有幾個重要的假設:

• 照片必須是single event，且必須在相同場景中。因為是利用3D空間來搜尋，所以如果照片來自不同的場景，就無法找出相對位置。
• 假設人在短時間內是相對靜止的，如果人在短時間內一直移動，就很難利用3D空間的相對位置來找人。

這篇paper提出的一個利用3D空間來搜尋人位置的想法是很特別方式，以及結合了一些圖片時間和人co-occurrence的特性，來增加找到的機會。

限制是，如果當人快速移動或是相同的人出現在不同場景中，這個方法就會失敗。

還有color base的appearance model，如果在場景中大家都穿相同的衣服(ex. 制服)，還是同一個part上有太多不同的顏色，就會造成辨認的效果不好。